Loading…

easyStringsLC #387Frequently asked

First Unique Character in a String

Q: How do you solve First Unique Character in a String using the Brute Force — Recount Per Character approach?

When to use it: Name it to set the baseline, then move to the two-pass counter. For each index `i`, count how many times `s[i]` occurs in the whole string; return `i` the first time that count is 1. If no index qualifies, return -1. **Why mention it.** It's the direct reading of 'non-repeating', and it's a clean baseline. But recounting the string for every character is quadratic — with `n` up to `10⁵` that's `10¹⁰` operations. Precomputing all frequencies once removes the repeated scans. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve First Unique Character in a String using the Frequency Count — Two Passes (Optimal) approach?

When to use it: The answer they want. Phrase it as 'count once, then find the first count-1 index'. First pass: tally each character's frequency into a table (an `int[26]` for lowercase English, or a hash map for Unicode). Second pass: walk the string left to right and return the index of the first character whose tally is exactly 1. If none qualifies, return -1. **Why two passes and why re-scan the string.** Frequencies are only fully known after seeing the whole string, so 'is this character unique?' can't be answered on the first pass. The second pass must iterate the *string* (not the map) because we need the leftmost *position*, and a hash map doesn't preserve input order. A 26-slot array does have a fixed order, but the index into it isn't the character's position in `s` — so we still scan `s`. Time complexity: O(n). Space complexity: O(1).

LCPractice

Arrays & Hashing · 9 of 83 · 6 min

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

In plain English

Among the characters that appear exactly once in the string, return the index of the leftmost one. If every character repeats, return -1.

Examples

Example 1

Input: s = "leetcode"
Output: 0
Note: 'l' appears once and is the first such character.

Example 2

Input: s = "loveleetcode"
Output: 2
Note: 'l' and 'o' repeat; 'v' at index 2 is the first with count 1.

Example 3

Input: s = "aabb"
Output: -1
Note: Every character repeats.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only lowercase English letters

Clarifying questions4First question: Return the index or the character?Explore questions

Q1.Return the index or the character?
The index of the first unique character. If none, return -1.
Q2.What characters can appear?
Lowercase English letters per constraints — so a 26-slot array works. For Unicode, use a hash map.
Q3.Is it case-sensitive?
Only lowercase here, so it doesn't arise. If mixed case, decide whether 'A' and 'a' are the same.
Q4.What if the string is one character?
That single character is unique → return 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Return the index of the first character that appears exactly once, or -1 if none. Two passes: pass one counts every character's frequency; pass two scans left to right and returns the first index whose count is 1. O(n) time, O(1) space for a fixed alphabet. The order check must scan the original string — iterating the map loses positional order.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you split the problem into a frequency tally plus an ordered scan, and whether you preserve positional order by re-scanning the string rather than the map.

Where candidates slip

Trying to answer in a single pass, or iterating the hash map for the 'first' index (map order isn't input order).

How to stand out

State the fixed-array O(1)-space claim, handle the all-repeats → -1 case explicitly, and mention the streaming follow-up that needs a queue.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recount Per Character	`O(n²)`	`O(1)`	Name it to set the baseline, then move to the two-pass counter.	Read
2	Frequency Count — Two Passes (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'count once, then find the first count-1 index'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewPass 1: count frequenciescount[c] == 1?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recount Per Character

TimeO(n²)SpaceO(1)

Name it to set the baseline, then move to the two-pass counter.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each character, how would you check whether it appears anywhere else?

2Hint 2Explore hint

For index i, scan the whole string counting occurrences of s[i]; the first with count 1 is the answer.

3Hint 3Explore hint

That's O(n²) — replace the per-character recount with a single precomputed frequency table.

A · Core idea

For each index i, count how many times s[i] occurs in the whole string; return i the first time that count is 1. If no index qualifies, return -1.

Why mention it. It's the direct reading of 'non-repeating', and it's a clean baseline. But recounting the string for every character is quadratic — with n up to 10⁵ that's 10¹⁰ operations. Precomputing all frequencies once removes the repeated scans.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aab"

i=0 'a'

count('a') = 2

Statenot unique

Final result2

C · Code with teaching comments

Reference implementation previewpublic int firstUniqChar(String s) { for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); int occurrences = 0; for (int j = 0; j < s.length(); j++) {Explore the full code

solution.javaJava

Brute Force — Recount Per Character — reference

2 teaching notes

1
public int firstUniqChar(String s) {
2
    for (int i = 0; i < s.length(); i++) {
3
        char c = s.charAt(i);
4
        int occurrences = 0;
5
        // Inner scan recounts the whole string for this character — the quadratic cost.
6
        for (int j = 0; j < s.length(); j++) {
7
            if (s.charAt(j) == c) occurrences++;
8
        }
9
        // First character seen exactly once, in left-to-right order.
10
        if (occurrences == 1) return i;
11
    }
12
    return -1;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The wasted work is recomputing the same frequencies n times. Tallying once into a table and then querying it is the standard count-then-use upgrade.

ComplexityO(n²) time, O(1) space — For each of n positions we scan up to n characters → O(n²). No extra structures beyond counters.

E · Edge cases and pitfalls2Calling s.count / inner scan repeatedly — O(n²) and slow on large inputs.Explore edge cases

Pitfalls

Calling s.count / inner scan repeatedly — O(n²) and slow on large inputs.
Returning the character instead of the index.

03.2

Approach 2 of 2 · Optimal

Frequency Count — Two Passes (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'count once, then find the first count-1 index'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you knew every character's total count before looking for the answer?

2Hint 2Explore hint

Pass 1: build a frequency table. Pass 2: scan the string and return the first index whose char has count 1.

3Hint 3Explore hint

For lowercase English the table is an int[26], so space is O(1).

A · Core idea

First pass: tally each character's frequency into a table (an int[26] for lowercase English, or a hash map for Unicode). Second pass: walk the string left to right and return the index of the first character whose tally is exactly 1. If none qualifies, return -1.

Why two passes and why re-scan the string. Frequencies are only fully known after seeing the whole string, so 'is this character unique?' can't be answered on the first pass. The second pass must iterate the string (not the map) because we need the leftmost position, and a hash map doesn't preserve input order. A 26-slot array does have a fixed order, but the index into it isn't the character's position in s — so we still scan s.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "loveleetcode"

Hash-map state

after pass 1

ValueIndex / state

l→ 2

o→ 2

v→ 1

e→ 4

t→ 1

Continue scanning

frequency table built

Final result2

C · Code with teaching comments

solution.javaJava

Frequency Count — Two Passes (Optimal) — optimal

3 teaching notes

1
public int firstUniqChar(String s) {
2
    int[] count = new int[26];
3
    for (int i = 0; i < s.length(); i++) {
4
        // Pass 1: build the 26-letter frequency histogram.
5
        count[s.charAt(i) - 'a']++;
6
    }
7
    for (int i = 0; i < s.length(); i++) {
8
        // Pass 2 over the STRING preserves left-to-right order to find the first
9
        // unique.
10
        if (count[s.charAt(i) - 'a'] == 1) {
11
            // Return the index, not the character.
12
            return i;
13
        }
14
    }
15
    return -1;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This cleanly separates two questions: 'how many of each?' (the table) and 'where is the first qualifying one?' (the ordered scan). Conflating them into one pass is what trips people up.

ComplexityO(n) time, O(1) space — Two linear passes over the string plus O(26) table work = O(n). The fixed-size table makes extra space O(1).

E · Edge cases and pitfalls5s = "aabb" — Every count is 2; pass 2 finds nothing → return -1.Explore edge cases

Edge cases handled

s = "aabb"Every count is 2; pass 2 finds nothing → return -1.
s = "z"Single character has count 1 → return 0.

Pitfalls

Iterating the map in pass 2 — its order isn't the string's order, so 'first' is wrong.
Trying to answer in one pass before all counts are known.
Using int[26] for Unicode input — switch to a hash map keyed by code point.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int firstUniqChar(String s) { int[] count = new int[26]; for (int i = 0; i < s.length(); i++) { count[s.charAt(i) - 'a']++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Scanning the map for the 'first' index

Hash maps don't preserve insertion/positional order reliably, so the first count-1 entry in the map may not be the first in the string. Re-scan the string.

Explore the code comparison

Don't write this

for c, n in count.items():
    if n == 1:
        return s.index(c)  # also O(n) per call, and order is map order

Write this instead

for i, c in enumerate(s):
    if count[c] == 1:
        return i

One-pass attempt

On the first pass you can't know a character is unique because a later duplicate may still appear. You need the full tally before locating the answer.

Explore the code comparison

Don't write this

// returns too early: 'l' looks unique before its second occurrence
for (int i = 0; i < s.length(); i++)
    if (seenOnce(s.charAt(i))) return i;

Write this instead

// pass 1 counts everything, pass 2 finds the first count==1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count + ordered re-scan

Code pattern to memorize

count = Counter(s)
for i, c in enumerate(s):
    if count[c] == 1: return i
return -1

Rules to remember

1Two passes: first count frequencies, then re-scan the string in order.
2Re-scan the string, not the map — only the string preserves left-to-right position.
3A fixed 26-slot array gives O(1) space for lowercase English; use a map for Unicode.
4Return the index, not the character; return -1 when every character repeats.
5Counting then querying separates 'how many' from 'where' — don't try to do both in one pass.

Use this pattern when

'First/only element with frequency exactly 1' over a sequence
Need positional answer after a global frequency tally
Any two-phase count-then-locate query on characters or values

Choose another pattern when

Need the unique element's value, order irrelevant → single XOR (Single Number)
Streaming with queries over time → a queue of candidates + counts (Design phase)
Need all unique characters, not the first → collect every count-1 entry

Interview takeaway

Count-then-rescan is the clean separation of 'tally frequencies' and 'find a position'. The frequency table is the same histogram used by Valid Anagram and Group Anagrams.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo-phase frequency-count then ordered scan. Reach for it whenever a positional answer depends on a global tally. The histogram is the same one behind Valid Anagram and Group Anagrams.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Anagram
Same character-frequency table, compared between two strings.
Sort Characters By Frequency
Coming soon
Count, then order characters by their frequency.
First Missing Positive
Coming soon
Different problem, same 'tally then scan for the first qualifying index' shape.

Same pattern

←

Valid Sudoku

Continue · Next problem

Majority Element

easyStringsLC #387Frequently asked

First Unique Character in a String

LCPractice

Arrays & Hashing · 9 of 83 · 6 min

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

In plain English

Among the characters that appear exactly once in the string, return the index of the leftmost one. If every character repeats, return -1.

Examples

Example 1

Input: s = "leetcode"
Output: 0
Note: 'l' appears once and is the first such character.

Example 2

Input: s = "loveleetcode"
Output: 2
Note: 'l' and 'o' repeat; 'v' at index 2 is the first with count 1.

Example 3

Input: s = "aabb"
Output: -1
Note: Every character repeats.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only lowercase English letters

Clarifying questions4First question: Return the index or the character?Explore questions

Q1.Return the index or the character?
The index of the first unique character. If none, return -1.
Q2.What characters can appear?
Lowercase English letters per constraints — so a 26-slot array works. For Unicode, use a hash map.
Q3.Is it case-sensitive?
Only lowercase here, so it doesn't arise. If mixed case, decide whether 'A' and 'a' are the same.
Q4.What if the string is one character?
That single character is unique → return 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you split the problem into a frequency tally plus an ordered scan, and whether you preserve positional order by re-scanning the string rather than the map.

Where candidates slip

Trying to answer in a single pass, or iterating the hash map for the 'first' index (map order isn't input order).

How to stand out

State the fixed-array O(1)-space claim, handle the all-repeats → -1 case explicitly, and mention the streaming follow-up that needs a queue.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recount Per Character	`O(n²)`	`O(1)`	Name it to set the baseline, then move to the two-pass counter.	Read
2	Frequency Count — Two Passes (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'count once, then find the first count-1 index'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recount Per Character

TimeO(n²)SpaceO(1)

Name it to set the baseline, then move to the two-pass counter.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each character, how would you check whether it appears anywhere else?

2Hint 2Explore hint

For index i, scan the whole string counting occurrences of s[i]; the first with count 1 is the answer.

3Hint 3Explore hint

That's O(n²) — replace the per-character recount with a single precomputed frequency table.

A · Core idea

For each index i, count how many times s[i] occurs in the whole string; return i the first time that count is 1. If no index qualifies, return -1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aab"

i=0 'a'

count('a') = 2

Statenot unique

Final result2

C · Code with teaching comments

solution.javaJava

Brute Force — Recount Per Character — reference

2 teaching notes

1
public int firstUniqChar(String s) {
2
    for (int i = 0; i < s.length(); i++) {
3
        char c = s.charAt(i);
4
        int occurrences = 0;
5
        // Inner scan recounts the whole string for this character — the quadratic cost.
6
        for (int j = 0; j < s.length(); j++) {
7
            if (s.charAt(j) == c) occurrences++;
8
        }
9
        // First character seen exactly once, in left-to-right order.
10
        if (occurrences == 1) return i;
11
    }
12
    return -1;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The wasted work is recomputing the same frequencies n times. Tallying once into a table and then querying it is the standard count-then-use upgrade.

ComplexityO(n²) time, O(1) space — For each of n positions we scan up to n characters → O(n²). No extra structures beyond counters.

E · Edge cases and pitfalls2Calling s.count / inner scan repeatedly — O(n²) and slow on large inputs.Explore edge cases

Pitfalls

Calling s.count / inner scan repeatedly — O(n²) and slow on large inputs.
Returning the character instead of the index.

03.2

Approach 2 of 2 · Optimal

Frequency Count — Two Passes (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'count once, then find the first count-1 index'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you knew every character's total count before looking for the answer?

2Hint 2Explore hint

Pass 1: build a frequency table. Pass 2: scan the string and return the first index whose char has count 1.

3Hint 3Explore hint

For lowercase English the table is an int[26], so space is O(1).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "loveleetcode"

Hash-map state

after pass 1

ValueIndex / state

l→ 2

o→ 2

v→ 1

e→ 4

t→ 1

Continue scanning

frequency table built

Final result2

C · Code with teaching comments

solution.javaJava

Frequency Count — Two Passes (Optimal) — optimal

3 teaching notes

1
public int firstUniqChar(String s) {
2
    int[] count = new int[26];
3
    for (int i = 0; i < s.length(); i++) {
4
        // Pass 1: build the 26-letter frequency histogram.
5
        count[s.charAt(i) - 'a']++;
6
    }
7
    for (int i = 0; i < s.length(); i++) {
8
        // Pass 2 over the STRING preserves left-to-right order to find the first
9
        // unique.
10
        if (count[s.charAt(i) - 'a'] == 1) {
11
            // Return the index, not the character.
12
            return i;
13
        }
14
    }
15
    return -1;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This cleanly separates two questions: 'how many of each?' (the table) and 'where is the first qualifying one?' (the ordered scan). Conflating them into one pass is what trips people up.

ComplexityO(n) time, O(1) space — Two linear passes over the string plus O(26) table work = O(n). The fixed-size table makes extra space O(1).

E · Edge cases and pitfalls5s = "aabb" — Every count is 2; pass 2 finds nothing → return -1.Explore edge cases

Edge cases handled

s = "aabb"Every count is 2; pass 2 finds nothing → return -1.
s = "z"Single character has count 1 → return 0.

Pitfalls

Iterating the map in pass 2 — its order isn't the string's order, so 'first' is wrong.
Trying to answer in one pass before all counts are known.
Using int[26] for Unicode input — switch to a hash map keyed by code point.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int firstUniqChar(String s) { int[] count = new int[26]; for (int i = 0; i < s.length(); i++) { count[s.charAt(i) - 'a']++; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Scanning the map for the 'first' index

Hash maps don't preserve insertion/positional order reliably, so the first count-1 entry in the map may not be the first in the string. Re-scan the string.

Explore the code comparison

Don't write this

for c, n in count.items():
    if n == 1:
        return s.index(c)  # also O(n) per call, and order is map order

Write this instead

for i, c in enumerate(s):
    if count[c] == 1:
        return i

One-pass attempt

On the first pass you can't know a character is unique because a later duplicate may still appear. You need the full tally before locating the answer.

Explore the code comparison

Don't write this

// returns too early: 'l' looks unique before its second occurrence
for (int i = 0; i < s.length(); i++)
    if (seenOnce(s.charAt(i))) return i;

Write this instead

// pass 1 counts everything, pass 2 finds the first count==1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count + ordered re-scan

Code pattern to memorize

count = Counter(s)
for i, c in enumerate(s):
    if count[c] == 1: return i
return -1

Rules to remember

1Two passes: first count frequencies, then re-scan the string in order.
2Re-scan the string, not the map — only the string preserves left-to-right position.
3A fixed 26-slot array gives O(1) space for lowercase English; use a map for Unicode.
4Return the index, not the character; return -1 when every character repeats.
5Counting then querying separates 'how many' from 'where' — don't try to do both in one pass.

Use this pattern when

'First/only element with frequency exactly 1' over a sequence
Need positional answer after a global frequency tally
Any two-phase count-then-locate query on characters or values

Choose another pattern when

Need the unique element's value, order irrelevant → single XOR (Single Number)
Streaming with queries over time → a queue of candidates + counts (Design phase)
Need all unique characters, not the first → collect every count-1 entry

Interview takeaway

Count-then-rescan is the clean separation of 'tally frequencies' and 'find a position'. The frequency table is the same histogram used by Valid Anagram and Group Anagrams.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Anagram
Same character-frequency table, compared between two strings.
Sort Characters By Frequency
Coming soon
Count, then order characters by their frequency.
First Missing Positive
Coming soon
Different problem, same 'tally then scan for the first qualifying index' shape.

Same pattern

←

Valid Sudoku

Continue · Next problem

Majority Element