First Unique Character in a String

🎯

First Unique Character in a String

easyHASH_MAPAmazonBloombergFacebook

Imagine you are analyzing a stream of characters from a chat app and want to quickly find the first character that hasn't repeated yet to highlight it.

💡 This problem is about counting how many times each character appears and then finding the first one that appears only once. Beginners often struggle because they try to solve it in one pass without storing counts, which is tricky.

📋

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.

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

💡

Example

Input"leetcode"

Output0

The first unique character is 'l' at index 0.

Input"loveleetcode"

Output2

The first unique character is 'v' at index 2.

Input"aabb"

Output-1

There is no unique character.

• Single character string → index 0
• All characters repeated → -1
• String with all unique characters → index 0
• String with unique character at the end → last index

⚠️

Common Mistakes

Checking uniqueness by comparing only adjacent characters

Incorrect output when duplicates are non-adjacent

✅ Use a frequency map to count all occurrences

Returning the character instead of its index

Fails problem requirement, wrong output format

✅ Return the index of the first unique character

Not handling the case when no unique character exists

Code may return wrong index or crash

✅ Return -1 explicitly if no unique character found

Using a data structure with high overhead for counting

Slower runtime or memory issues

✅ Use hash maps or arrays optimized for character sets

Modifying the input string during iteration

Runtime errors or incorrect results

✅ Do not mutate input; use separate data structures

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly checking each character against all others. It’s simple but inefficient, helping beginners understand the problem deeply before optimizing.

Intuition

Check each character and scan the entire string to see if it repeats. The first character that never repeats is the answer.

Algorithm

1. For each character in the string,
2. Check every other character to see if it matches.
3. If no match is found, return the current index.
4. If all characters repeat, return -1.

💡 The nested loops make it hard to see efficiency, but it clearly shows the uniqueness check.

</>

Code

def firstUniqChar(s: str) -> int:
    n = len(s)
    for i in range(n):
        unique = True
        for j in range(n):
            if i != j and s[i] == s[j]:
                unique = False
                break
        if unique:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    print(firstUniqChar('leetcode'))  # Output: 0
    print(firstUniqChar('loveleetcode'))  # Output: 2
    print(firstUniqChar('aabb'))  # Output: -1

Line Notes

for i in range(n):Outer loop picks each character to test uniqueness

unique = TrueAssume current character is unique until proven otherwise

for j in range(n):Inner loop compares current character with all others

if i != j and s[i] == s[j]:Check if another character matches current one

unique = FalseMark as not unique if duplicate found

breakStop inner loop early once duplicate found

if unique:If no duplicates found, return current index

return -1No unique character found in entire string

public class Solution {
    public static int firstUniqChar(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            boolean unique = true;
            for (int j = 0; j < n; j++) {
                if (i != j && s.charAt(i) == s.charAt(j)) {
                    unique = false;
                    break;
                }
            }
            if (unique) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(firstUniqChar("leetcode")); // 0
        System.out.println(firstUniqChar("loveleetcode")); // 2
        System.out.println(firstUniqChar("aabb")); // -1
    }
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop selects each character to check

boolean unique = true;Assume character is unique initially

for (int j = 0; j < n; j++) {Inner loop compares with all other characters

if (i != j && s.charAt(i) == s.charAt(j)) {Check for duplicate character

unique = false;Mark as not unique if duplicate found

break;Stop inner loop early to save time

if (unique) return i;Return index if character is unique

return -1;Return -1 if no unique character found

#include <iostream>
#include <string>
using namespace std;

int firstUniqChar(string s) {
    int n = s.size();
    for (int i = 0; i < n; i++) {
        bool unique = true;
        for (int j = 0; j < n; j++) {
            if (i != j && s[i] == s[j]) {
                unique = false;
                break;
            }
        }
        if (unique) return i;
    }
    return -1;
}

int main() {
    cout << firstUniqChar("leetcode") << endl; // 0
    cout << firstUniqChar("loveleetcode") << endl; // 2
    cout << firstUniqChar("aabb") << endl; // -1
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop picks each character to test

bool unique = true;Assume character is unique initially

for (int j = 0; j < n; j++) {Inner loop compares with all other characters

if (i != j && s[i] == s[j]) {Check if duplicate character exists

unique = false;Mark as not unique if duplicate found

break;Stop inner loop early to save time

if (unique) return i;Return index if unique character found

return -1;Return -1 if no unique character found

function firstUniqChar(s) {
    const n = s.length;
    for (let i = 0; i < n; i++) {
        let unique = true;
        for (let j = 0; j < n; j++) {
            if (i !== j && s[i] === s[j]) {
                unique = false;
                break;
            }
        }
        if (unique) return i;
    }
    return -1;
}

// Test cases
console.log(firstUniqChar('leetcode')); // 0
console.log(firstUniqChar('loveleetcode')); // 2
console.log(firstUniqChar('aabb')); // -1

Line Notes

for (let i = 0; i < n; i++) {Outer loop selects each character

let unique = true;Assume character is unique initially

for (let j = 0; j < n; j++) {Inner loop compares with all other characters

if (i !== j && s[i] === s[j]) {Check for duplicate character

unique = false;Mark as not unique if duplicate found

break;Stop inner loop early to save time

if (unique) return i;Return index if unique character found

return -1;Return -1 if no unique character found

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each character, we scan the entire string to check duplicates, resulting in n * n operations.

💡 For n=1000, this means about 1,000,000 comparisons, which is slow for large inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for big strings but helps understand the problem before optimizing.

🧠

Frequency Map with Two Passes

💡 This approach uses a hash map to count frequencies in one pass, then finds the first unique character in a second pass. It’s much faster and a common interview solution.

Intuition

Count how many times each character appears, then scan the string again to find the first character with count 1.

Algorithm

1. Create a frequency map to count each character's occurrences.
2. Iterate over the string and update counts in the map.
3. Iterate over the string again and check the frequency map.
4. Return the index of the first character with frequency 1, or -1 if none.

💡 Separating counting and checking makes the logic clear and efficient.

</>

Code

def firstUniqChar(s: str) -> int:
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    print(firstUniqChar('leetcode'))  # 0
    print(firstUniqChar('loveleetcode'))  # 2
    print(firstUniqChar('aabb'))  # -1

Line Notes

freq = {}Initialize empty dictionary to store character counts

for ch in s:Count frequency of each character in string

freq[ch] = freq.get(ch, 0) + 1Increment count for current character

for i, ch in enumerate(s):Second pass to find first unique character

if freq[ch] == 1:Check if character is unique

return iReturn index of first unique character

return -1Return -1 if no unique character found

import java.util.*;
public class Solution {
    public static int firstUniqChar(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char ch : s.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (freq.get(s.charAt(i)) == 1) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(firstUniqChar("leetcode")); // 0
        System.out.println(firstUniqChar("loveleetcode")); // 2
        System.out.println(firstUniqChar("aabb")); // -1
    }
}

Line Notes

Map<Character, Integer> freq = new HashMap<>();Create map to store character counts

for (char ch : s.toCharArray()) {Count frequency of each character

freq.put(ch, freq.getOrDefault(ch, 0) + 1);Increment count for character

for (int i = 0; i < s.length(); i++) {Second pass to find first unique character

if (freq.get(s.charAt(i)) == 1) return i;Return index if character is unique

return -1;Return -1 if no unique character found

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int firstUniqChar(string s) {
    unordered_map<char, int> freq;
    for (char ch : s) {
        freq[ch]++;
    }
    for (int i = 0; i < (int)s.size(); i++) {
        if (freq[s[i]] == 1) return i;
    }
    return -1;
}

int main() {
    cout << firstUniqChar("leetcode") << endl; // 0
    cout << firstUniqChar("loveleetcode") << endl; // 2
    cout << firstUniqChar("aabb") << endl; // -1
    return 0;
}

Line Notes

unordered_map<char, int> freq;Hash map to count character frequencies

for (char ch : s) {Count frequency of each character

freq[ch]++;Increment count for character

for (int i = 0; i < (int)s.size(); i++) {Second pass to find first unique character

if (freq[s[i]] == 1) return i;Return index if character is unique

return -1;Return -1 if no unique character found

function firstUniqChar(s) {
    const freq = new Map();
    for (const ch of s) {
        freq.set(ch, (freq.get(ch) || 0) + 1);
    }
    for (let i = 0; i < s.length; i++) {
        if (freq.get(s[i]) === 1) return i;
    }
    return -1;
}

// Test cases
console.log(firstUniqChar('leetcode')); // 0
console.log(firstUniqChar('loveleetcode')); // 2
console.log(firstUniqChar('aabb')); // -1

Line Notes

const freq = new Map();Initialize map to store character counts

for (const ch of s) {Count frequency of each character

freq.set(ch, (freq.get(ch) || 0) + 1);Increment count for character

for (let i = 0; i < s.length; i++) {Second pass to find first unique character

if (freq.get(s[i]) === 1) return i;Return index if character is unique

return -1;Return -1 if no unique character found

⏱

Complexity

TimeO(n)

SpaceO(1)

Two passes over the string, each O(n). Frequency map size is limited to 26 lowercase letters, so space is constant.

💡 For n=100000, this means about 200000 operations, which is efficient and fast.

Interview Verdict: Accepted and efficient

This is the standard solution to code in interviews for this problem.

🧠

Single Pass with Index Tracking

💡 This approach tracks the first occurrence index of each character and counts frequency simultaneously, then finds the minimum index of unique characters. It’s a slight optimization in logic but similar complexity.

Intuition

Store the index of the first occurrence of each character and count how many times it appears. Then pick the smallest index with count 1.

Algorithm

1. Initialize a map to store character counts and a map for first occurrence indices.
2. Iterate over the string once, updating counts and recording first indices.
3. Iterate over the counts to find characters with frequency 1.
4. Return the minimum index among unique characters or -1 if none.

💡 This approach combines counting and indexing to avoid a second string scan for uniqueness check.

</>

Code

def firstUniqChar(s: str) -> int:
    freq = {}
    first_index = {}
    for i, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1
        if ch not in first_index:
            first_index[ch] = i
    min_index = len(s)
    for ch, count in freq.items():
        if count == 1 and first_index[ch] < min_index:
            min_index = first_index[ch]
    return min_index if min_index != len(s) else -1

# Driver code
if __name__ == '__main__':
    print(firstUniqChar('leetcode'))  # 0
    print(firstUniqChar('loveleetcode'))  # 2
    print(firstUniqChar('aabb'))  # -1

Line Notes

freq = {}Dictionary to count character frequencies

first_index = {}Dictionary to store first occurrence indices

for i, ch in enumerate(s):Single pass to update counts and indices

freq[ch] = freq.get(ch, 0) + 1Increment frequency count

if ch not in first_index:Record first occurrence index only once

min_index = len(s)Initialize min index to max possible

for ch, count in freq.items():Check all characters for uniqueness

if count == 1 and first_index[ch] < min_index:Update min index if unique character found

return min_index if min_index != len(s) else -1Return earliest unique index or -1

import java.util.*;
public class Solution {
    public static int firstUniqChar(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        Map<Character, Integer> firstIndex = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
            firstIndex.putIfAbsent(ch, i);
        }
        int minIndex = s.length();
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            if (entry.getValue() == 1) {
                minIndex = Math.min(minIndex, firstIndex.get(entry.getKey()));
            }
        }
        return minIndex == s.length() ? -1 : minIndex;
    }

    public static void main(String[] args) {
        System.out.println(firstUniqChar("leetcode")); // 0
        System.out.println(firstUniqChar("loveleetcode")); // 2
        System.out.println(firstUniqChar("aabb")); // -1
    }
}

Line Notes

Map<Character, Integer> freq = new HashMap<>();Map to count character frequencies

Map<Character, Integer> firstIndex = new HashMap<>();Map to store first occurrence indices

for (int i = 0; i < s.length(); i++) {Single pass over string

freq.put(ch, freq.getOrDefault(ch, 0) + 1);Increment frequency count

firstIndex.putIfAbsent(ch, i);Record first occurrence index only once

int minIndex = s.length();Initialize min index to max possible

for (Map.Entry<Character, Integer> entry : freq.entrySet()) {Iterate over frequency map

if (entry.getValue() == 1) {Check if character is unique

minIndex = Math.min(minIndex, firstIndex.get(entry.getKey()));Update min index if smaller

return minIndex == s.length() ? -1 : minIndex;Return earliest unique index or -1

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;

int firstUniqChar(string s) {
    unordered_map<char, int> freq;
    unordered_map<char, int> firstIndex;
    for (int i = 0; i < (int)s.size(); i++) {
        char ch = s[i];
        freq[ch]++;
        if (firstIndex.find(ch) == firstIndex.end()) {
            firstIndex[ch] = i;
        }
    }
    int minIndex = INT_MAX;
    for (auto& p : freq) {
        if (p.second == 1) {
            minIndex = min(minIndex, firstIndex[p.first]);
        }
    }
    return minIndex == INT_MAX ? -1 : minIndex;
}

int main() {
    cout << firstUniqChar("leetcode") << endl; // 0
    cout << firstUniqChar("loveleetcode") << endl; // 2
    cout << firstUniqChar("aabb") << endl; // -1
    return 0;
}

Line Notes

unordered_map<char, int> freq;Map to count character frequencies

unordered_map<char, int> firstIndex;Map to store first occurrence indices

for (int i = 0; i < (int)s.size(); i++) {Single pass over string

freq[ch]++;Increment frequency count

if (firstIndex.find(ch) == firstIndex.end()) {Record first occurrence index only once

int minIndex = INT_MAX;Initialize min index to max int

for (auto& p : freq) {Iterate over frequency map

if (p.second == 1) {Check if character is unique

minIndex = min(minIndex, firstIndex[p.first]);Update min index if smaller

return minIndex == INT_MAX ? -1 : minIndex;Return earliest unique index or -1

function firstUniqChar(s) {
    const freq = new Map();
    const firstIndex = new Map();
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        freq.set(ch, (freq.get(ch) || 0) + 1);
        if (!firstIndex.has(ch)) firstIndex.set(ch, i);
    }
    let minIndex = s.length;
    for (const [ch, count] of freq.entries()) {
        if (count === 1) {
            minIndex = Math.min(minIndex, firstIndex.get(ch));
        }
    }
    return minIndex === s.length ? -1 : minIndex;
}

// Test cases
console.log(firstUniqChar('leetcode')); // 0
console.log(firstUniqChar('loveleetcode')); // 2
console.log(firstUniqChar('aabb')); // -1

Line Notes

const freq = new Map();Map to count character frequencies

const firstIndex = new Map();Map to store first occurrence indices

for (let i = 0; i < s.length; i++) {Single pass over string

freq.set(ch, (freq.get(ch) || 0) + 1);Increment frequency count

if (!firstIndex.has(ch)) firstIndex.set(ch, i);Record first occurrence index only once

let minIndex = s.length;Initialize min index to max possible

for (const [ch, count] of freq.entries()) {Iterate over frequency map

if (count === 1) {Check if character is unique

minIndex = Math.min(minIndex, firstIndex.get(ch));Update min index if smaller

return minIndex === s.length ? -1 : minIndex;Return earliest unique index or -1

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass to count and record indices, then iterate over map of at most 26 keys.

💡 For large n, this is efficient and uses constant extra space due to limited alphabet.

Interview Verdict: Accepted and efficient

This approach is a slight variation but equally good for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the frequency map two-pass approach for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Frequency Map with Two Passes	O(n)	O(1)	No	N/A	Code this approach in interviews
3. Single Pass with Index Tracking	O(n)	O(1)	No	N/A	Optional mention or code if comfortable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the frequency map two-pass approach as the optimal solution.Step 4: Optionally mention the single pass index tracking approach.Step 5: Code the frequency map approach with clear variable names.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your ability to optimize from brute force to efficient hash map usage, handle edge cases, and write clean code.

Common Follow-ups

• What if the string contains Unicode characters? → Use a hash map that supports Unicode keys.
• Can you solve it in one pass? → Yes, by tracking indices and counts simultaneously.

💡 Follow-ups test your ability to adapt solutions to different input types and optimize passes.

🔍

Pattern Recognition

When to Use

1) Need to find unique or frequency-based info; 2) Input is a string or array; 3) Constraints allow hash map usage; 4) Output depends on order or index.

Signature Phrases

first non-repeating characterunique characterfrequency of characters

NOT This Pattern When

Problems requiring substring or subsequence dynamic programming, or sorting-based approaches

Similar Problems

Longest Substring Without Repeating Characters - uses frequency and sliding windowValid Anagram - uses frequency countingGroup Anagrams - uses frequency or sorted keys

Practice

1. You are given an array of integers and need to determine if any value appears at least twice. Which approach guarantees the most efficient detection of duplicates in terms of time complexity?

easy

A. Sort the array and then scan once to check if any adjacent elements are equal.

B. Use a hash set to track seen elements and check membership while iterating once.

C. Use nested loops to compare every pair of elements for equality.

D. Use dynamic programming to build a table of duplicate occurrences.

Solution

1. Step 1: Understand the problem requirements

   The problem requires detecting duplicates efficiently in an array.

2. Step 2: Compare approaches based on time complexity

   Sorting then scanning is O(n log n), nested loops is O(n²), and dynamic programming is unnecessary here. Using a hash set allows O(n) time with O(n) space by checking membership during one pass.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set membership check is O(1) average, enabling linear time detection [OK]

Hint: Hash set membership check enables linear time detection [OK]

Common Mistakes:

• Confusing sorting approach as optimal
• Thinking nested loops are efficient enough
• Misapplying DP to a membership problem

2. Given the following code snippet, what is the final output when calling isHappy(7)?

def sum_of_squares(num):
    return sum(int(d) ** 2 for d in str(num))

UNHAPPY_CYCLE = {4, 16, 37, 58, 89, 145, 42, 20}

def isHappy(n: int) -> bool:
    while n != 1 and n not in UNHAPPY_CYCLE:
        n = sum_of_squares(n)
    return n == 1

print(isHappy(7))

easy

A. false

B. true

C. The code runs infinitely

D. Raises a runtime error

Solution

1. Step 1: Trace sum_of_squares for n=7

   7 -> 7² = 49

2. Step 2: Iterate until n=1 or cycle detected

   49 -> 4²+9²=16+81=97 -> 9²+7²=81+49=130 -> 1²+3²+0²=1+9+0=10 -> 1²+0²=1 -> loop ends, returns true

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   7 is a happy number, code returns true [OK]

Hint: Trace sum_of_squares until 1 or cycle [OK]

Common Mistakes:

• Assuming 7 leads to cycle or infinite loop

3. You are given an integer array and need to find the k elements that appear most frequently. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a frequency map and bucket sort to group elements by their frequency, then collect top k from highest frequency buckets.

B. Sort the entire array and pick the top k elements by frequency.

C. Use a greedy approach that picks elements as they appear until k elements are chosen.

D. Use dynamic programming to build frequency counts and select top k elements.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding top k frequent elements efficiently, ideally in linear time.

2. Step 2: Identify approach with linear time complexity

   Bucket sort groups elements by frequency, allowing O(n) time retrieval of top k elements by scanning buckets from high to low frequency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort approach is known to run in O(n) time for this problem [OK]

Hint: Bucket sort groups by frequency for O(n) retrieval [OK]

Common Mistakes:

• Sorting entire array is O(n log n), not optimal
• Greedy approach ignores frequency counts
• DP is unrelated to frequency counting here

4. Consider the following Python code implementing the optimal bucket sort approach for top K frequent elements. What is the value of res just before the function returns when called with nums = [1,2,2,3] and k = 2?

easy

A. [1, 2]

B. [2, 1]

C. [2, 3]

D. [3, 2]

Solution

1. Step 1: Calculate frequency map for nums=[1,2,2,3]

   freq = {1:1, 2:2, 3:1}, max_freq = 2

2. Step 2: Fill buckets and collect top k=2 elements

   buckets = [[], [1,3], [2]]; iterate from freq=2 down: add 2, then freq=1 add 1; res = [2,1]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order depends on bucket insertion; here 2 appears before 1 [OK]

Hint: Trace buckets from highest frequency down [OK]

Common Mistakes:

• Confusing order of elements in buckets
• Assuming sorted order inside buckets
• Off-by-one in frequency indexing

5. What is the time and space complexity of the optimal solution using prefix sums and a hash map (or array) for the longest subarray with sum divisible by k problem, given an input array of length n and integer k?

medium

A. Time: O(n log n), Space: O(n)

B. Time: O(n), Space: O(k)

C. Time: O(n * k), Space: O(n)

D. Time: O(n^2), Space: O(1)

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates once over the array (length n), performing O(1) operations per element, so time is O(n).

2. Step 2: Analyze space complexity

   We store earliest indices for each remainder modulo k, so space is O(k), independent of n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time and space proportional to k [OK]

Hint: Prefix sums + hash map -> O(n) time, O(k) space [OK]

Common Mistakes:

• Confusing nested loops complexity with prefix sum approach
• Assuming space is O(n) due to prefix sums stored
• Thinking time is O(n*k) due to modulo operations