Definition
- First non-repeating character – the earliest character in the string that appears exactly once.
- LinkedHashMap – a
HashMapsubclass that preserves the insertion order of keys, so iterating it yields characters in first-seen order. - Two-pass algorithm – pass one counts frequencies; pass two iterates the map and returns the first key whose value is one.
- Alternative – a plain
HashMapfor counts plus a rescan of the original string is equally O(n). - Complexity – O(n) time for two passes, O(k) space for k distinct characters.
At National Bank of India, the teller scans a stream of transaction type codes and needs the first code that occurred only once, since a singleton can flag an unusual one-off operation. The teller tallies every code in order, then reads the tally from the start and picks the first code with a tally of exactly one.
Understanding the Concepts
What is the first non-repeating character problem?
Given a string, find the first character that appears exactly once. If no such character exists, return a sentinel value. The problem has two parts: counting occurrences and preserving order so you know which unique character came first.
package com.bank.core;
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstUniqueLinkedHashMap {
public static Character firstUnique(String s) {
Map<Character, Integer> freq = new LinkedHashMap<>();
for (char c : s.toCharArray()) {
freq.merge(c, 1, Integer::sum);
}
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
if (entry.getValue() == 1) return entry.getKey();
}
return null;
}
public static void main(String[] args) {
System.out.println(firstUnique("settlement")); // s
System.out.println(firstUnique("aabb")); // null
}
}
s
null
Why choose LinkedHashMap over HashMap?
A plain HashMap does not remember the order in which keys were inserted. If you iterate a HashMap, the entries come out in an unpredictable order, so you cannot determine which unique character came first from the map alone.
A LinkedHashMap keeps keys in insertion order. Because you insert a character the first time you see it, the map's iteration order is exactly the order characters first appeared in the string. This lets you iterate the map directly and return the first entry with count one.
package com.bank.core;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class OrderComparison {
public static void main(String[] args) {
String input = "banking";
Map<Character, Integer> linked = new LinkedHashMap<>();
Map<Character, Integer> plain = new HashMap<>();
for (char c : input.toCharArray()) {
linked.merge(c, 1, Integer::sum);
plain.merge(c, 1, Integer::sum);
}
System.out.println("LinkedHashMap order: " + linked.keySet());
System.out.println("HashMap order: " + plain.keySet());
}
}
LinkedHashMap order: [b, a, n, k, i, g]
HashMap order: [a, b, g, i, k, n]
How does the HashMap plus string rescan alternative work?
If you prefer a plain HashMap for counting, you can rescan the original string in a second pass and return the first character whose count is one. The string itself provides the correct order.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class HashMapRescan {
public static Character firstUnique(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
for (char c : s.toCharArray()) {
if (freq.get(c) == 1) return c;
}
return null;
}
public static void main(String[] args) {
System.out.println(firstUnique("transaction")); // r
}
}
r
How does the fixed-array approach work?
For lowercase ASCII input, an int[26] array is the fastest option. It avoids all hashing overhead and uses constant space. The trade-off is that it only works for a known, small character set.
package com.bank.core;
public class FixedArrayFirstUnique {
public static int firstUniqueIndex(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) freq[c - 'a']++;
for (int i = 0; i < s.length(); i++) {
if (freq[s.charAt(i) - 'a'] == 1) return i;
}
return -1;
}
public static void main(String[] args) {
String code = "payments";
int idx = firstUniqueIndex(code);
if (idx >= 0) {
System.out.println("First unique: '" + code.charAt(idx) + "' at index " + idx);
}
}
}
First unique: 'p' at index 0
What are the edge cases?
Edge cases include empty strings, strings where every character repeats, strings where every character is unique, and single-character strings.
package com.bank.core;
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstUniqueEdgeCases {
public static Character firstUnique(String s) {
Map<Character, Integer> freq = new LinkedHashMap<>();
for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
for (var e : freq.entrySet()) if (e.getValue() == 1) return e.getKey();
return null;
}
public static void main(String[] args) {
System.out.println("Empty: " + firstUnique(""));
System.out.println("All repeat: " + firstUnique("aabbcc"));
System.out.println("All unique: " + firstUnique("xyz"));
System.out.println("Single: " + firstUnique("a"));
}
}
Empty: null
All repeat: null
All unique: x
Single: a
What about the streaming variant?
If characters arrive one at a time and you need the current first unique character at any moment, use a queue of candidates combined with a count map. Each new character updates the count and is enqueued. To answer a query, poll characters from the front of the queue, discarding any whose count has risen above one, until the front is truly unique.
package com.bank.service;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class StreamingUnique {
private final Map<Character, Integer> count = new HashMap<>();
private final Queue<Character> queue = new LinkedList<>();
public void add(char c) {
count.merge(c, 1, Integer::sum);
queue.add(c);
}
public Character firstUnique() {
while (!queue.isEmpty() && count.get(queue.peek()) > 1) queue.poll();
return queue.isEmpty() ? null : queue.peek();
}
public static void main(String[] args) {
StreamingUnique s = new StreamingUnique();
for (char c : "aabcb".toCharArray()) {
s.add(c);
System.out.println("After '" + c + "': " + s.firstUnique());
}
}
}
After 'a': a
After 'a': null
After 'b': b
After 'c': b
After 'b': c
What is the time and space complexity?
All three approaches (LinkedHashMap, HashMap + rescan, fixed array) run in O(n) time with two passes. The LinkedHashMap and HashMap approaches use O(k) space for k distinct characters. The fixed-array approach uses O(1) space because the array size is constant at 26 regardless of input length. The streaming variant processes each character in amortised O(1) time.
What is the banking use case?
At National Bank of India, Rajesh processes compact strings of single-character transaction type codes and surfaces the first one-off code among many repeats. A one-off transaction type can flag an unusual operation for review by Priya. When every code repeats, the system returns a clean empty result and logs the observation.
package com.bank.service;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Optional;
public class TransactionCodeAnalyzer {
public static Optional<Character> firstOneOffCode(String codes) {
Map<Character, Integer> freq = new LinkedHashMap<>();
for (char c : codes.toCharArray()) freq.merge(c, 1, Integer::sum);
for (var entry : freq.entrySet()) {
if (entry.getValue() == 1) return Optional.of(entry.getKey());
}
return Optional.empty();
}
public static void main(String[] args) {
String codes = "DDTWWDTP"; // D=Deposit, T=Transfer, W=Withdrawal, P=Payment
Optional<Character> unique = firstOneOffCode(codes);
unique.ifPresentOrElse(
c -> System.out.println("Flag one-off code: " + c),
() -> System.out.println("No one-off codes found")
);
}
}
Flag one-off code: P
Visual Overview
First Non-Repeating Character (LinkedHashMap) ══════════════════════════════════════════════ Input: "settlement" Pass 1: Build frequency map (insertion order preserved) ┌───────────────────────────────────────────────┐ │ s:1 e:3 t:3 l:1 m:1 n:1 │ │ (order: s, e, t, l, m, n) │ └───────────────────────────────────────────────┘ Pass 2: Iterate map in insertion order s → count=1 → FOUND! Return 's' LinkedHashMap vs HashMap ════════════════════════ LinkedHashMap: [s, e, t, l, m, n] ← insertion order HashMap: [e, l, m, n, s, t] ← unpredictable order
Key Takeaway
The first non-repeating character problem finds the earliest character in a string that appears exactly once. The LinkedHashMap approach solves it in two linear passes: pass one counts each character's frequency, and because LinkedHashMap preserves insertion order, pass two iterates the map and returns the first key with count one.
Choosing LinkedHashMap over a plain HashMap is deliberate: a plain HashMap loses the first-seen order, so you would need to rescan the original string to find which unique character came first. The LinkedHashMap version is elegant because the order lives in the map itself. For a known small alphabet like lowercase ASCII, a fixed int[26] array is faster and uses constant space, and you rescan the string to find the first index with count one.
The streaming variant is a natural follow-up where characters arrive one at a time and you need the current first unique character at any moment. A queue of candidates combined with a count map handles this efficiently.
In the banking project at National Bank of India, Rajesh uses this on compact transaction type code strings to surface the first one-off code for review. Explaining why LinkedHashMap preserves order, the fixed-array alternative for known alphabets, and the streaming follow-up shows the interviewer that you understand both the solution and the constraints that would change the approach.
Remember one sentence: use a LinkedHashMap to count frequencies in insertion order, then iterate and return the first key with count one for an O(n) solution.
---