Definition
- First non-repeating character – the earliest character in the string that appears exactly once.
- LinkedHashMap approach – count frequency in one pass; because
LinkedHashMappreserves insertion order, iterate it and return the first key with count one. - Plain HashMap alternative – count with a
HashMap, then rescan the original string and return the first character whose count is one. - Fixed array – for lowercase ASCII, use
int[26]for counts and rescan the string; constant space. - Complexity – O(n) time for two passes, O(k) space where k is the number of distinct characters.
National Bank of India generates coupon codes and needs to pick the first unique letter as a sub-key. A clerk tallies every letter in order, then reads the tally from the start and reports the first letter that appeared exactly once.
Understanding the Concepts
What does first non-repeating character mean?
The first non-repeating character is the earliest character in the string that appears exactly once. In the string "savings", every letter appears once except s which appears twice. The first non-repeating character is a because it is the earliest character with a frequency of one.
package com.bank.core;
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstNonRepeating {
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> e : freq.entrySet()) {
if (e.getValue() == 1) return e.getKey();
}
return null;
}
public static void main(String[] args) {
System.out.println(firstUnique("savings")); // a
System.out.println(firstUnique("aabb")); // null
}
}
a
null
Why use a LinkedHashMap instead of a HashMap?
A LinkedHashMap preserves the order in which keys were first inserted. When you iterate its entries, they come out in insertion order, which is the order characters first appeared in the string. This lets you find the first unique character directly from the map.
A plain HashMap does not guarantee any iteration order. If you use a HashMap, you would need to rescan the original string in order and look up each character's count to find the first unique one.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class HashMapAlternative {
// Using plain HashMap + string rescan
public static Character firstUnique(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.merge(c, 1, Integer::sum);
}
// Rescan the string to find the first with count 1
for (char c : s.toCharArray()) {
if (freq.get(c) == 1) return c;
}
return null;
}
public static void main(String[] args) {
System.out.println(firstUnique("rajesh")); // r (all unique, first one)
}
}
r
How does the fixed-array approach work for a known alphabet?
If the input contains only lowercase ASCII letters, a fixed int[26] array is faster and uses constant space. Count frequencies in the first pass, then rescan the string and return the first character whose count is one.
package com.bank.core;
public class FixedArrayApproach {
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 = "settlement";
int idx = firstUniqueIndex(code);
System.out.println("Index: " + idx + ", Char: " + (idx >= 0 ? code.charAt(idx) : "none"));
}
}
Index: 1, Char: e
How do the three approaches compare?
| Feature | LinkedHashMap | HashMap + rescan | int[26] array |
|---|---|---|---|
| Preserves order | Yes, in the map | No, rescan string | No, rescan string |
| Space | O(k) distinct chars | O(k) distinct chars | O(1) fixed 26 slots |
| Character set | Any Unicode | Any Unicode | Lowercase ASCII only |
| Speed constant | Moderate (hashing overhead) | Moderate | Fastest (array access) |
| Time | O(n) | O(n) | O(n) |
package com.bank.core;
public class ApproachComparison {
public static void main(String[] args) {
String input = "bankaccount";
// All three produce the same answer: 'b' (first unique character)
System.out.println("LinkedHashMap: " + linkedHashMap(input));
System.out.println("HashMap+rescan: " + hashMapRescan(input));
System.out.println("Array: " + fixedArray(input));
}
static Character linkedHashMap(String s) {
java.util.Map<Character, Integer> m = new java.util.LinkedHashMap<>();
for (char c : s.toCharArray()) m.merge(c, 1, Integer::sum);
for (var e : m.entrySet()) if (e.getValue() == 1) return e.getKey();
return null;
}
static Character hashMapRescan(String s) {
java.util.Map<Character, Integer> m = new java.util.HashMap<>();
for (char c : s.toCharArray()) m.merge(c, 1, Integer::sum);
for (char c : s.toCharArray()) if (m.get(c) == 1) return c;
return null;
}
static Character fixedArray(String s) {
int[] f = new int[26];
for (char c : s.toCharArray()) f[c - 'a']++;
for (char c : s.toCharArray()) if (f[c - 'a'] == 1) return c;
return null;
}
}
LinkedHashMap: b
HashMap+rescan: b
Array: b
What are the edge cases?
Edge cases include empty strings, strings where all characters repeat, strings where all characters are 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("")); // null
System.out.println("All repeat: " + firstUnique("aabb")); // null
System.out.println("All unique: " + firstUnique("abc")); // a
System.out.println("Single: " + firstUnique("z")); // z
}
}
Empty: null
All repeat: null
All unique: a
Single: z
What about the streaming variant?
If characters arrive one at a time and you need to answer the first unique character at any moment, a queue of candidates combined with a count map gives an efficient online algorithm. You add each character to the count map and enqueue it if it is new. Then poll from the queue, discarding characters whose count has risen above one, until the front is a true unique character.
package com.bank.service;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class StreamingFirstUnique {
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) {
StreamingFirstUnique stream = new StreamingFirstUnique();
String codes = "aabcbd";
for (char c : codes.toCharArray()) {
stream.add(c);
System.out.println("After '" + c + "': first unique = " + stream.firstUnique());
}
}
}
After 'a': first unique = a
After 'a': first unique = null
After 'b': first unique = b
After 'c': first unique = b
After 'b': first unique = c
After 'd': first unique = c
What is the time and space complexity?
Both the LinkedHashMap and the plain HashMap approaches run in O(n) time, making two linear passes. The space is O(k) where k is the number of distinct characters, which is bounded by the alphabet size. For the fixed int[26] array approach, space is O(1) because the array size is constant regardless of input length.
What is the banking use case?
At National Bank of India, Rajesh uses this to derive a sub-key for promotional coupon codes. From a generated code, the system picks the first letter that appears only once, which reduces collisions in a secondary index. When no character is unique, such as a code where every letter repeats, the system returns a clear sentinel so Priya's code can fall back to another key-generation strategy.
package com.bank.service;
import java.util.LinkedHashMap;
import java.util.Map;
public class CouponSubKey {
public static String deriveSubKey(String couponCode) {
Map<Character, Integer> freq = new LinkedHashMap<>();
for (char c : couponCode.toCharArray()) {
freq.merge(c, 1, Integer::sum);
}
for (var entry : freq.entrySet()) {
if (entry.getValue() == 1) {
return String.valueOf(entry.getKey());
}
}
return "FALLBACK"; // no unique character
}
public static void main(String[] args) {
System.out.println("SubKey: " + deriveSubKey("SAVER")); // S (all unique)
System.out.println("SubKey: " + deriveSubKey("AABB")); // FALLBACK
}
}
SubKey: S
SubKey: FALLBACK
Visual Overview
First Non-Repeating Character
═════════════════════════════
Input: "settlement"
Pass 1: Count frequencies (LinkedHashMap preserves order)
┌───┬───┬───┬───┬───┬───┬───┐
│ s │ e │ t │ l │ m │ n │ │
│ 1 │ 3 │ 3 │ 1 │ 1 │ 1 │ │
└───┴───┴───┴───┴───┴───┴───┘
(insertion order preserved)
Pass 2: Iterate map, find first count == 1
s → count=1 → FOUND! Return 's'
Key Takeaway
Finding the first non-repeating character means finding the earliest character in the string that appears exactly once. The standard solution uses two passes with a LinkedHashMap: the first pass counts the frequency of every character, and because LinkedHashMap preserves insertion order, the second pass iterates the map and returns the first character whose count is one.
Choosing a LinkedHashMap over a plain HashMap is the deliberate decision. A plain HashMap counts correctly but loses the first-seen order, so you would need to rescan the original string to determine which unique character came first. The LinkedHashMap version is elegant because the order lives in the map. For a known small alphabet like lowercase ASCII, a fixed int[26] array is even faster and uses constant space, and you rescan the string to find the first index with count one.
In the banking project at National Bank of India, Rajesh uses this to derive a sub-key for promotional coupon codes. From a generated code, the system picks the first letter that appears only once. When no character is unique, the system returns a clear fallback so Priya's code can use another key-generation strategy. The streaming variant with a queue of candidates is a natural follow-up that interviewers like to ask about.
Remember one sentence: count frequencies in a LinkedHashMap to preserve insertion order, then iterate and return the first key with count one for O(n) time.
---