First Non-repeating Character
Mahabharata — The Unique Voice — The First Warrior Who Speaks Only Once
बहुजनेषु एकः अद्वितीयः — प्रथमः स कः?। गणनया ज्ञात्वा — अनन्यं प्रथमतः दर्शय॥
*Among many, one is unique — who is the first such? Count and know — show the first who stands alone.*
The Story
Given a string, find the index of the first non-repeating character. If none exists, return -1.
For `s = "leetcode"`: 'l' appears once → index 0. For `s = "loveleetcode"`: 'l' appears twice, 'o' appears twice, 'v' once at index 2 → return 2.
In Yudhishthira's court, many warriors shouted their names. The king wanted to know: "Who was the FIRST warrior to announce themselves and NOT be echoed by anyone else?"
**Two-pass frequency count:**
Pass 1: Count frequency of each character. Pass 2: Find the FIRST character with frequency 1.
```java 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; ```
Trace `"leetcode"`: Pass 1: l=1, e=2, t=1, c=1, o=1, d=1 Pass 2: i=0, 'l', freq=1 → return 0 ✓
Trace `"aabb"`: Pass 1: a=2, b=2 Pass 2: all frequencies > 1 → return -1 ✓
"The first pass knows all frequencies," Yudhishthira noted. "The second pass finds the first with exactly one occurrence — preserving the ORIGINAL ORDER, which is why we need two passes."
**Why O(1) space?** The frequency array has fixed size 26 (lowercase English letters only). This doesn't grow with input size.
The Double-Loop Checker
For each character, check if it appears anywhere else in the string. First one that doesn't is the answer. O(n²).
public int firstUniqCharBruteForce(String s) {
for (int i = 0; i < s.length(); i++) {
boolean unique = true;
for (int j = 0; j < s.length(); j++)
if (i != j && s.charAt(i) == s.charAt(j)) { unique = false; break; }
if (unique) return i;
}
return -1;
}The Two-Pass Frequency Wisdom
public int firstUniqChar(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;
}Step-by-Step Walkthrough
s="cc" freq: c=2 Pass2: i=0'c'(2), i=1'c'(2) Return -1 ✅
Deep Insight
**Why two passes and not one?** In a single pass, we don't know if a character seen once will repeat later. Only after seeing the full string can we confirm frequency.
**LinkedHashMap alternative:** For arbitrary characters (not just lowercase English), use `LinkedHashMap<Character, Integer>` for frequency. LinkedHashMap preserves insertion order, so the first entry with value 1 in the map is the answer. But still O(26) = O(1) effectively for ASCII.
**The fixed 26-array trick:** Whenever the problem specifies "lowercase English letters", `int[26]` with `char - 'a'` indexing is O(1) space and faster than a HashMap.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Double nested loop |
| Optimal | O(n) | O(1) | Fixed 26-element array — not dependent on n |
Pattern Recognition
✅ Two-pass frequency count ✅ int[26] for lowercase letters (O(1) space) ✅ Second pass finds FIRST occurrence with freq==1 ✅ Return -1 if none found **LeetCode Trigger Phrases:** → "first unique character in a string" → "first non-repeating character" → Frequency + order preservation
Bhagavad Gita 6.30
यो मां पश्यति सर्वत्र सर्वं च मयि पश्यति। तस्याहं न प्रणश्यामि स च मे न प्रणश्यति॥
For one who sees Me everywhere and sees everything in Me, I am never lost, nor is that person ever lost to Me.
Connection: The first non-repeating character stands alone in the crowd — unique, unrepeated, and therefore most clearly 'seen'. The frequency array sees every character equally, counting each appearance without judgment. Then the second pass finds the one who appeared just once — the true individual in a world of repetition. Like the yogi who sees the divine clearly (without repetitive distraction), the algorithm finds the singular truth after accounting for all occurrences.