First Unique Character in a String — The Frequency Map Pattern Every Amazon Interview Tests

Problem Statement#

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input:  s = "leetcode"
Output: 0
Explanation: 'l' appears exactly once and is the first such character (index 0).

Example 2:

Input:  s = "loveleetcode"
Output: 2
Explanation: 'l' appears twice, 'o' appears twice — 'v' at index 2 appears once.

Example 3:

Input:  s = "aabb"
Output: -1
Explanation: Every character appears more than once. No unique character exists.

Constraints:

• 1 <= s.length <= 100,000
• s consists of only lowercase English letters

Why This Problem Matters#

LeetCode 387 appears regularly in Amazon phone screens and has been reported in interviews at Google, Bloomberg, and Meta. It looks trivial on the surface — count characters, find the first one with count 1. But that is exactly why interviewers love it.

The real test is not whether you can solve it. Every candidate who reaches an interview loop can solve this problem with enough time. The real test is whether you solve it the right way, in the right order, and then handle the follow-ups without flinching.

Here is what a senior engineer is looking for when they ask this question:

Do you think about space complexity? The string only contains lowercase letters, which means the alphabet is fixed at 26 characters. A frequency array of size 26 is O(1) space — not O(n). Candidates who reflexively reach for a dictionary without thinking about this reveal that they do not reason about data structure choices.

Do you understand why two passes are necessary (or are they)? Some candidates try to do this in one pass and get confused. Others do two passes but cannot articulate why. The two-pass approach is clean and intentional — the first pass gives you global frequency information, which the second pass uses to make a local decision at each index. You cannot know whether a character is unique until you have seen the entire string.

Can you handle the follow-ups? What if the string comes from a stream? What if you need to handle Unicode instead of just lowercase letters? What if the string is enormous and you need to minimize passes? These escalations are where interviewers separate good from great.

Solve this problem well, and you demonstrate mastery of the frequency map pattern — one of the most fundamental tools in string and array interviews.

The Core Insight#

Before writing any code, ask yourself: what does it mean for a character to be "unique"?

It means it appears exactly once in the entire string. Not twice. Not three times. Exactly once.

So the fundamental question you need to answer for each character is: how many times does this character appear in the whole string?

You cannot answer that question while you are still scanning the string. If you are at index 2 and you see the character 'v', you do not yet know whether it will appear again at index 10 or 50. You have to finish scanning the entire string first.

This is the core reason a two-pass solution is the natural fit:

Pass 1 — Build global knowledge: Scan the entire string and count how many times each character appears. After this pass, you know everything about character frequencies.

Pass 2 — Find the first unique: Scan the string again, left to right, and return the index of the first character whose frequency is exactly 1.

The critical insight about space: the string contains only lowercase English letters. There are exactly 26 of them. No matter how long the string is — whether it has 10 characters or 100,000 — you only ever need to track 26 possible characters. That means your frequency structure is constant size. This is an O(1) space solution, not O(n). Make sure you say this out loud in your interview. It is the difference between an average answer and a strong one.

Why not a HashMap? A HashMap would also work and is a perfectly correct solution. But for a fixed alphabet, a 26-element array indexed by character - 'a' is faster in practice (direct array access vs. hash computation) and uses less memory. The HashMap approach is better when you cannot assume a fixed alphabet — for example, if the string can contain Unicode characters.

Visual Dry Run#

Let us trace through s = "loveleetcode" step by step.

Pass 1: Count frequencies

We scan left to right and increment a counter for each character. The 26-element array (indexed 0-25 for 'a'-'z') builds up like this:

s = "loveleetcode"
     0123456789...
 
After scanning each character:
  'l' → freq['l'-'a'] = freq[11]++  → 1
  'o' → freq['o'-'a'] = freq[14]++  → 1
  'v' → freq['v'-'a'] = freq[21]++  → 1
  'e' → freq['e'-'a'] = freq[4]++   → 1
  'l' → freq[11]++                   → 2  (l seen again)
  'e' → freq[4]++                    → 2  (e seen again)
  'e' → freq[4]++                    → 3
  't' → freq['t'-'a'] = freq[19]++  → 1
  'c' → freq['c'-'a'] = freq[2]++   → 1
  'o' → freq[14]++                   → 2  (o seen again)
  'd' → freq['d'-'a'] = freq[3]++   → 1
  'e' → freq[4]++                    → 4

Final frequency state for characters that appear:

Pass 2: Find first character with frequency 1

Now we scan left to right again, checking each character's count:

We return index 2 because 'v' is the first character that appears exactly once.

Notice that even though 't', 'c', and 'd' are also unique, they appear later in the string. We return the first unique character, so we stop at index 2 the moment we find 'v'.

Common Mistakes#

These are not hypothetical errors — they are the actual mistakes candidates make in real interviews under time pressure.

Mistake 1: Returning the character instead of the index.

The problem asks for the index of the first unique character, not the character itself. The output for "leetcode" is 0, not 'l'. Under pressure it is easy to write return c or return char instead of return i. Always re-read what the problem asks you to return before you finalize your solution.

Mistake 2: Assuming the answer is always the least-frequent character overall.

This is a subtle logic error. "First unique" means the leftmost character that appears exactly once — not the character that appears the fewest times overall. Consider "abcabc": every character appears twice, so the answer is -1. But if the input were "abcab", then 'c' appears once and is the answer at index 2. The minimum frequency in the entire string is 1, and you return the index of the leftmost character with that frequency. Do not conflate "minimum frequency character" with "first unique character."

Mistake 3: Trying to find the answer in a single pass and getting the logic wrong.

A common mistake is trying to maintain a "current best candidate" while scanning once. For example: "if I see a new character, it is a candidate; if I see it again, remove it." This fails because you might discard a candidate that later turns out to be the answer, or because you need to compare positions of multiple candidates. The two-pass approach is cleaner and provably correct — do not sacrifice clarity for a dubious optimization.

Mistake 4: Using s.count(c) inside the second loop (Python).

A very common Python mistake is:

for i, c in enumerate(s):
    if s.count(c) == 1:   # ← This is O(n) per iteration!
        return i

This looks clean but is actually O(n²) time because s.count(c) scans the entire string for each character. It will pass LeetCode's weak test cases but fails in interviews when the interviewer asks about complexity. Always build the frequency map first, then look up in O(1).

Mistake 5: Off-by-one or wrong indexing with the frequency array.

When using an array instead of a dictionary, the index for character c is ord(c) - ord('a') in Python or c.charCodeAt(0) - 97 in JavaScript. A slip here — like forgetting the offset, or using c - 'a' in Python where c is a string (not an integer) — causes an immediate crash. Always verify your index arithmetic before writing it in an interview.

Solutions#

Approach 1 — Two-Pass with 26-Element Array (Optimal for Fixed Alphabet)#

This is the canonical solution for strings containing only lowercase English letters. O(n) time, O(1) space.

Python

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # A fixed-size array of 26 elements — one slot per lowercase letter.
        # This is O(1) space because the size never grows with the input.
        freq = [0] * 26
 
        # Pass 1: Count how many times each character appears.
        # ord(c) - ord('a') maps 'a'→0, 'b'→1, ..., 'z'→25
        for c in s:
            freq[ord(c) - ord('a')] += 1
 
        # Pass 2: Scan left to right and return the index of the
        # first character whose global frequency is exactly 1.
        for i, c in enumerate(s):
            if freq[ord(c) - ord('a')] == 1:
                return i  # First unique character found — return its index
 
        # No character appeared exactly once — return -1 per the spec
        return -1

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
function firstUniqChar(s) {
    // Fixed-size array of 26 slots — one per lowercase letter.
    // O(1) space regardless of the length of s.
    const freq = new Array(26).fill(0);
 
    // Pass 1: Build frequency counts.
    // charCodeAt(0) gives the ASCII code; subtracting 97 ('a') gives 0-25.
    for (let i = 0; i < s.length; i++) {
        freq[s.charCodeAt(i) - 97]++;
    }
 
    // Pass 2: Walk left to right; return the index of the first char
    // whose count in the frequency array is exactly 1.
    for (let i = 0; i < s.length; i++) {
        if (freq[s.charCodeAt(i) - 97] === 1) {
            return i; // This is the leftmost unique character
        }
    }
 
    // Every character appeared more than once
    return -1;
}

Approach 2 — Two-Pass with HashMap (Handles Any Alphabet)#

Use this when the string can contain characters outside the 26 lowercase letters — digits, uppercase, Unicode, symbols. The HashMap scales with the number of distinct characters, not with the input length.

Python

from collections import Counter
 
class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Counter builds a frequency map in one pass.
        # Works for any characters — not just lowercase letters.
        freq = Counter(s)
 
        # Second pass: return the index of the first character
        # whose count in the Counter is exactly 1.
        for i, c in enumerate(s):
            if freq[c] == 1:
                return i
 
        return -1

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
function firstUniqChar(s) {
    // Build a Map from character to its frequency.
    // A Map (not a plain object) correctly handles any key type.
    const freq = new Map();
 
    // Pass 1: Count occurrences of every character
    for (const c of s) {
        freq.set(c, (freq.get(c) || 0) + 1);
    }
 
    // Pass 2: Find the leftmost character with frequency exactly 1
    for (let i = 0; i < s.length; i++) {
        if (freq.get(s[i]) === 1) {
            return i;
        }
    }
 
    return -1;
}

Approach 3 — indexOf + lastIndexOf (Clever, But Know the Tradeoff)#

A concise one-liner that works by checking whether the first and last occurrence of a character are the same index. If they are, the character appears exactly once.

Python

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # For each character in the alphabet, find the first occurrence.
        # If its first and last occurrence are the same index, it is unique.
        # Take the minimum such index across all 26 letters.
        result = min(
            (s.index(c) for c in 'abcdefghijklmnopqrstuvwxyz'
             if s.index(c) == s.rindex(c)),
            default=-1
        )
        return result

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
function firstUniqChar(s) {
    let result = Infinity;
 
    // Iterate over each letter of the alphabet
    for (let code = 97; code <= 122; code++) {
        const c = String.fromCharCode(code);
        const first = s.indexOf(c);
 
        // Character not in string — skip
        if (first === -1) continue;
 
        // If first and last occurrence are the same, character is unique
        if (first === s.lastIndexOf(c)) {
            // Track the smallest (leftmost) index among all unique characters
            result = Math.min(result, first);
        }
    }
 
    return result === Infinity ? -1 : result;
}

This approach iterates over 26 letters and calls indexOf / lastIndexOf for each, giving O(26 * n) = O(n) time with O(1) space. It is clean and interview-friendly, but the two-pass array solution is more explicitly correct and easier to explain under pressure. Use this one as a follow-up to show range.

Complexity Analysis#

Two-Pass with 26-Element Array#

Two-Pass with HashMap#

indexOf + lastIndexOf (Alphabet Scan)#

Key interview point: The 26-element array and the HashMap both achieve O(n) time. The difference is in space and generality. For a fixed lowercase alphabet, the array solution is strictly better — O(1) vs. O(k) space. For arbitrary character sets, the HashMap is the only correct option. State both and explain when you would choose each.

Follow-up Questions#

These are the actual follow-up escalations that appear in Amazon, Google, and Bloomberg interviews after you solve the base problem.

Q1: What if the string contains uppercase letters, digits, or Unicode characters?

The 26-element array breaks down because the index arithmetic c - 'a' is only valid for lowercase letters. Switch to a HashMap: the keys are the characters themselves, and the values are their counts. The algorithm is identical — two passes, same logic. The HashMap approach generalizes to any character set. This is why it is good practice to clarify the character set constraint before writing your solution.

Q2: What if the string arrives as a data stream — you cannot store the entire string?

This is the trickiest follow-up. You cannot do a second pass because you only see each character once. The streaming variant uses a different data structure: a LinkedHashMap (ordered dictionary) that maps each character to its count, preserving insertion order.

• When a character arrives for the first time, add it to the map with count 1.
• When it arrives again, increment its count to 2 (or higher).

To find the first unique character at any point, scan the LinkedHashMap in insertion order and return the first key whose value is 1. This gives O(1) space (bounded by 26 keys for lowercase letters) and O(1) amortized update time per character.

In Python, collections.OrderedDict preserves insertion order. In JavaScript, a regular Map preserves insertion order. The query "what is the current first unique character?" takes O(k) time where k is the number of distinct characters seen so far — O(1) for lowercase-only inputs.

Q3: What if you need to return all unique characters, not just the first one?

Change the return logic: instead of stopping at the first character with frequency 1, collect all indices where freq[c] == 1 and return them as a list. Maintain the left-to-right order from Pass 2 to preserve position ordering. Time and space remain O(n).

Q4: What if the string can be mutated — characters can be removed — and you need to always return the current first unique character efficiently?

Now we need a dynamic data structure. Use a combination of:

• A frequency HashMap to track counts.
• A doubly linked list (or a LinkedHashMap) to maintain the candidates in order.

When a character's count drops to 1, add it back to the candidate list. When it goes above 1, remove it. The head of the linked list is always the answer. This supports both character removal and first-unique queries in O(1) amortized time.

Q5: Can you do this in a single pass?

For the standard problem (fixed string, return index), a true single-pass solution is not possible in the general case because "first unique" requires global frequency information that you only have after seeing the whole string. However, you can combine both passes conceptually: build the frequency array, then the second pass is just an O(n) scan. Some interviewers accept the indexOf + lastIndexOf approach as "conceptually single-pass" from the caller's perspective — know what your interviewer means when they ask this.

This Pattern Solves#

The two-pass frequency map pattern from this problem directly applies to:

• LeetCode 451 — Sort Characters By Frequency: Build a frequency map (same Pass 1), then sort by count descending (different use of the same data structure).
• LeetCode 242 — Valid Anagram: Build a frequency map for both strings and compare — same 26-element array trick.
• LeetCode 438 — Find All Anagrams in a String: Sliding window frequency comparison — same counting mechanism, applied dynamically.
• LeetCode 169 — Majority Element: Frequency counting to find the element appearing more than n/2 times.
• LeetCode 884 — Uncommon Words from Two Sentences: Count word frequencies across two sentences, return words with global frequency 1 — conceptually identical to this problem at the word level.

Any time you see "find the element that appears exactly once" or "find the element with a specific frequency," your instinct should immediately reach for the two-pass frequency map.

Key Takeaways#

• LeetCode 387 — First Unique Character in a String is an Easy problem asked at Amazon, Bloomberg, and Google; it tests the two-pass "learn then decide" pattern.
• You cannot identify uniqueness in one pass without backtracking — always count frequencies in pass 1, then find the first count-1 index in pass 2.
• A 26-element integer array (indexed by ord(c) - ord('a')) is faster and uses less memory than a HashMap for lowercase-only inputs.
• Use a HashMap (or Counter) when the character set is arbitrary (Unicode, digits, symbols) — mention this pivot proactively.
• Time O(n), space O(1) for the frequency array (bounded by 26 characters regardless of input length).
• The "build global info first, then local decisions" two-phase habit recurs in prefix sums, graph coloring, and sliding-window problems.
• Return -1 if no unique character is found — forgetting this edge case is the most common interview mistake on this problem.