Log inSign up
easyleetcodeNot Started

First Unique Character in a String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

Input: s = "leetcode"
Output: 0
Explanation: The character l at index 0 is the first character that does not occur at any other index.

Example 2 · Example:

Input: s = "loveleetcode"
Output: 2
Explanation: The character v at index 2 is the first non-repeating character.

Example 3 · Example:

Input: s = "aabb"
Output: -1
Explanation: No unique character exists in the string.

Constraints:

  • 1 <= s.length <= 105
  • s consists of only lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master two-pass hash counting for order preservation.
  • Avoid quadratic built-in search methods (indexOf).
  • Adapt the algorithm for data stream scenarios using queues.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding the first/earliest unique or non-repeating item in a sequence.
  • When ordering of appearance matters among filtered elements.

Algorithmic Decision Tree:

  • Two-Pass Frequency Counting
  • Streaming Queue / Linked HashMap

Connected Patterns:

First Non-Repeating Character in a StreamSort Characters By FrequencyIsomorphic Strings

1. Nested Scanning (Brute Force)

Intuition

For each index i from 0 to n - 1, compare s[i] with every other character s[j] where j != i. If no match is found, s[i] is unique and we return i immediately. If all characters repeat, return -1.

When to apply: Exploratory concept only.

Algorithm

  1. Loop i from 0 to n - 1:
  2. Set isUnique = true.
  3. Loop j from 0 to n - 1:
  4. If i != j and s[i] == s[j]: isUnique = false; break.
  5. If isUnique is true, return i.
  6. Return -1.

Nested Scanning All Pairs Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [l, e, e, t, c, o, d, e]
Current operationSTEP 1 OF 6
Observation: Fix outer pointer at candidate i = 0 ('l')
Visual state
Values and pointers at this exact step
array
S
l
e
e
t
c
o
d
e
0
↑ i=0 ('l')
1
2
3
4
5
6
7
Variables at this step
Candidate Index
0
Char
'l'
Inner Scan
1..7
Check / comparison
Outer loop fixes i = 0 ('l'). Test if 'l' repeats in s[1..7].
Decision / next transition
Initialize inner scan j = 1 to 7 looking for matching 'l'.
Why this step matters

Observation: Fix outer pointer at candidate i = 0 ('l').

Decision: Scan remaining characters j = 1 through 7.

Invariant: If no s[j] == s[0], index 0 is the first non-repeating character.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int firstUniqChar(std::string s) {
7 int n = s.size();
8 for (int i = 0; i < n; ++i) {
9 bool unique = true;
10 for (int j = 0; j < n; ++j) {
11 if (i != j && s[i] == s[j]) {
12 unique = false;
13 break;
14 }
15 }
16 if (unique) return i;
17 }
18 return -1;
19 }
20};
21
22int main() {
23 Solution sol;
24 std::cout << sol.firstUniqChar("leetcode") << std::endl; // 0
25 std::cout << sol.firstUniqChar("loveleetcode") << std::endl; // 2
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(N^2) — Nested loops examine all pairs of characters.
  • Space complexity: O(1)

Why Brute Force Doesn't Scale:

Using a direct integer array index (char - 'a') eliminates hash table lookup overhead.

Only 26 integers of stack memory are used (O(1) space).

2. Queue / Streaming First-Pass Approach

Intuition

Maintain a count array and a queue of pairs (char, index). As each character arrives, increment its count and push (char, index) to queue. Simultaneously, pop elements from the front of the queue while the front character's count is > 1. At the end, the front of the queue contains the earliest unique character.

When to apply: When characters arrive sequentially as a stream and cannot be stored or re-scanned.

Algorithm

  1. Initialize count[26] = {0} and a queue of pair<char, int>.
  2. For each character s[i], increment count[s[i] - 'a'] and push {s[i], i} to queue.
  3. While queue is not empty and count[queue.front().first - 'a'] > 1, pop from queue.
  4. If queue is empty, return -1; otherwise return queue.front().second.

Queue / LinkedHashMap Streaming Frequency First-Pass

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [l, e, e, t, c, o, d, e]
Current operationSTEP 1 OF 6
Observation: First character s[0]='l'
Visual state
Values and pointers at this exact step
array
S
l:0
0
↑ i=0 ('l')
Variables at this step
Queue Head
('l', 0)
Seen Count
{"l":1}
Check / comparison
Process s[0]='l'. First time seen. Record in queue with index 0.
Decision / next transition
Queue holds [('l', 0)]. Candidate queue head is 'l'.
Why this step matters

Observation: First character s[0]='l'. Maintain queue of unique candidates with their indices.

Decision: Enqueue ('l', 0).

Invariant: Head of queue represents current candidate for first unique character.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <queue>
5
6class Solution {
7public:
8 int firstUniqChar(std::string s) {
9 int count[26] = {0};
10 std::queue<std::pair<char, int>> q;
11
12 for (int i = 0; i < (int)s.size(); ++i) {
13 count[s[i] - 'a']++;
14 q.push({s[i], i});
15
16 while (!q.empty() && count[q.front().first - 'a'] > 1) {
17 q.pop();
18 }
19 }
20
21 return q.empty() ? -1 : q.front().second;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.firstUniqChar("loveleetcode") << std::endl; // 2
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) — Each character is pushed and popped from the queue at most once.
  • Space complexity: O(1) (queue holds at most 26 unique characters)

3. Two-Pass Frequency Array (Optimal)

Intuition

Initialize an integer array freq of size 26 with zeros. Pass 1: traverse s and increment freq[s[i] - 'a']. Pass 2: traverse s again from index 0 to n - 1. Check freq[s[i] - 'a']: if it is equal to 1, return i. If loop terminates without finding any such character, return -1.

When to apply: The standard gold standard solution for memory efficiency and execution speed.

Algorithm

  1. Create int freq[26] = {0}.
  2. Loop c in s: increment freq[c - 'a'].
  3. Loop i from 0 to s.length - 1:
  4. If freq[s[i] - 'a'] == 1, return i.
  5. Return -1.

Fixed 26-Array Frequency Pre-computation & First Uniq Scan

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [l, e, e, t, c, o, d, e]
Current operationSTEP 1 OF 6
Observation: In Pass 1, build frequency table: 'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1
Visual state
Values and pointers at this exact step
array
S
l
e
e
t
c
o
d
e
0
↑ Pass 1: Count freqs
1
2
3
4
5
6
7
Variables at this step
Pass
1 (Frequency Map)
Frequencies
{ l: 1, e: 3, t: 1, c: 1, o: 1, d: 1 }
Check / comparison
Scan s to populate character frequency table.
Decision / next transition
Counts: { l: 1, e: 3, t: 1, c: 1, o: 1, d: 1 }.
Why this step matters

Observation: In Pass 1, build frequency table: 'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1.

Decision: Begin Pass 2 from index 0 to find the first character with count === 1.

Invariant: First index with frequency 1 is the first non-repeating character.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int firstUniqChar(std::string s) {
7 int freq[26] = {0};
8 for (char c : s) {
9 freq[c - 'a']++;
10 }
11 for (int i = 0; i < (int)s.size(); ++i) {
12 if (freq[s[i] - 'a'] == 1) {
13 return i;
14 }
15 }
16 return -1;
17 }
18};
19
20int main() {
21 Solution sol;
22 std::cout << sol.firstUniqChar("leetcode") << std::endl; // 0
23 std::cout << sol.firstUniqChar("loveleetcode") << std::endl; // 2
24 std::cout << sol.firstUniqChar("aabb") << std::endl; // -1
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N) — Performs exactly 2 linear passes over the string with fixed 26-element array.
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force Nested ScanningO(N^2)O(1)No extra memory.Quadratic time complexity, will TLE on N = 105.
2.Queue / LinkedHashMap (Single Pass of Input)O(N)O(1) (<= 26 entries)Ideal for streaming data where input cannot be rewound.Queue overhead.
3.Two-Pass Frequency ArrayOptimalO(N)O(1) extra spaceSimplest, fastest runtime, zero heap allocations.Requires two passes over the input string.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating through the 26 frequency buckets instead of the string in pass 2 (which gives alphabetical order rather than string appearance order).

Pitfall 2:

Using indexOf == lastIndexOf inside a loop which results in O(N2) complexity.

Crucial Edge Cases to Validate:

  • All characters repeat (e.g., aabbcc): Second pass finishes without finding freq == 1, returns -1.
  • String has length 1 (e.g., z): freq[z]=1, second pass returns 0 on first iteration.
  • Unique character is at the very last index (e.g., aaab): Second pass reaches index 3 and correctly returns 3.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether the input is streaming or in-memory. For streaming, mention the Queue approach; for in-memory, use the 2-pass array.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the second loop iterate over the original string s rather than the 26 frequency buckets?

Back to DSA Sheet