First Unique Character in a String

📋

Problem

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.

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.

Edge cases: Single character string → index 0All characters repeated → -1String with all unique characters → index 0

</>

IDE

def firstUniqChar(s: str) -> int:public int firstUniqChar(String s)int firstUniqChar(string s)function firstUniqChar(s)

def firstUniqChar(s: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int firstUniqChar(String s) {
        // Write your solution here
        return -1;
    }
}

#include <string>
using namespace std;

int firstUniqChar(string s) {
    // Write your solution here
    return -1;
}

function firstUniqChar(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: -1 when unique character existsReturning -1 prematurely without scanning entire string after frequency count.✅ After counting frequencies, iterate entire string to find first character with count 1 and return its index.

Wrong: Index of first character that appears unique so far (greedy)Stopping at first character that appears unique without full frequency count.✅ Use two-pass approach: first count frequencies, then find first unique character in second pass.

Wrong: Wrong index due to off-by-one errorIncorrect loop bounds or indexing when scanning string.✅ Ensure loops run from 0 to len(s)-1 and return correct index without subtracting or adding incorrectly.

Wrong: Timeout or no output for large inputUsing nested loops or O(n^2) approach instead of O(n).✅ Implement frequency counting with hash map or array in O(n) time.

Wrong: Incorrect index due to miscounting repeated charactersConfusing presence with frequency, counting only once per character.✅ Count exact frequency of each character, not just presence.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly.

Watch out for common algorithmic traps like greedy and indexing errors.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"s":"leetcode"}

Expected0

⏱ Performance - must finish in 2000ms

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

💡 Try counting the frequency of each character first.

💡 Use a hash map to store character counts, then find the first with count 1.

💡 Return the index of the first character with frequency 1 in the original string.

Why it failed: Returned wrong index or -1 despite unique character at index 0. Fix: Use two passes - first count frequencies, second find first char with count 1. This is the canonical basic case test.

✓ Correctly identified the first unique character index.

t1_02basic

Input{"s":"loveleetcode"}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Check frequency counts for all characters.

💡 Ensure you scan the string in order after counting frequencies.

💡 Return the index of the first character with frequency 1, here index 2.

Why it failed: Returned wrong index or -1 despite unique character at index 2. Fix: After frequency count, iterate string to find first char with count 1. This is a standard basic case.

✓ Correctly found the first unique character index.

t2_01edge

Input{"s":"a"}

Expected0

⏱ Performance - must finish in 2000ms

Single character string, so index 0 is unique by default.

💡 Consider the smallest input size possible.

💡 A single character is always unique.

💡 Return 0 immediately if string length is 1.

Why it failed: Returned -1 or wrong index for single character string. Fix: Handle single character input by returning 0 immediately or via frequency count. This is the single element edge case.

✓ Correctly handled single character input.

t2_02edge

Input{"s":"aabbcc"}

Expected-1

⏱ Performance - must finish in 2000ms

All characters repeated, so no unique character exists.

💡 Check if any character has frequency 1 after counting.

💡 If none found, return -1.

💡 Ensure you don't return an index for repeated characters.

Why it failed: Returned index >=0 despite no unique characters. Fix: After frequency count, if no char has count 1, return -1. This is the all repeated characters edge case.

✓ Correctly returned -1 when no unique character exists.

t2_03edge

Input{"s":"abcdef"}

Expected0

⏱ Performance - must finish in 2000ms

All characters unique, so first character at index 0 is the answer.

💡 Check frequency counts carefully.

💡 All counts will be 1, so return index 0.

💡 Ensure you don't skip the first character if unique.

Why it failed: Returned -1 or wrong index when all characters are unique. Fix: Return index of first character with count 1, which is 0 here. This is the all unique characters edge case.

✓ Correctly returned 0 for all unique characters.

t2_04edge

Input{"s":"aabbccd"}

Expected6

⏱ Performance - must finish in 2000ms

Unique character 'd' is at the last index 6.

💡 Check frequency counts for all characters.

💡 Unique character might be at the end of the string.

💡 Return the last index if that character is unique.

Why it failed: Returned -1 or wrong index missing unique character at end. Fix: After frequency count, iterate entire string to find first unique char, including last index. This is the unique at end edge case.

✓ Correctly identified unique character at last index.

t3_01corner

Input{"s":"aabbccddeeffg"}

Expected12

⏱ Performance - must finish in 2000ms

Unique character 'g' at index 12, tests greedy approach failure.

💡 Don't stop at first character that appears unique in partial scan.

💡 Use full frequency map before deciding unique character.

💡 Two-pass approach ensures correct first unique character index.

Why it failed: Returned index less than 12 due to greedy early return. Fix: Use two-pass frequency counting instead of greedy single pass. This is the greedy trap corner case.

✓ Correctly avoided greedy trap and found unique character at index 12.

t3_02corner

Input{"s":"abcabcabcabcx"}

Expected12

⏱ Performance - must finish in 2000ms

Unique character 'x' at index 12, tests 0/1 vs unbounded confusion.

💡 Each character counted only once per occurrence.

💡 Don't confuse repeated characters with unique ones.

💡 Ensure frequency counts reflect exact occurrences.

Why it failed: Returned -1 or wrong index due to miscounting repeated characters. Fix: Count exact frequency of each character, not just presence. This is the 0/1 vs unbounded confusion test.

✓ Correctly counted frequencies and found unique character at index 12.

t3_03corner

Input{"s":"aabbccddeeffggh"}

Expected14

⏱ Performance - must finish in 2000ms

Unique character 'h' at index 14, tests off-by-one errors.

💡 Check indexing carefully when iterating string.

💡 Ensure last character is included in frequency and search.

💡 Return correct index without off-by-one mistakes.

Why it failed: Returned index 13 or -1 due to off-by-one error. Fix: Iterate full string length and return correct index. This is the off-by-one corner case.

✓ Correctly handled indexing and found unique character at index 14.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000, solution must run in O(n) time within 2 seconds.

💡 Use O(n) frequency counting with hash map or array.

💡 Avoid nested loops or repeated scanning.

💡 Two-pass linear scan is efficient enough for this input size.

Why it failed: Solution times out due to O(n^2) or worse complexity. Fix: Use O(n) two-pass frequency counting approach. This is the performance test catching inefficient complexity.

✓ Solution runs efficiently in O(n) time for large input.

Practice

1. 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

2. The following code attempts to check if two strings are isomorphic:

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    s_to_t = {}
    for c1, c2 in zip(s, t):
        if c1 in s_to_t:
            if s_to_t[c1] != c2:
                return False
        else:
            s_to_t[c1] = c2
    return True

What is the bug in this code?

medium

A. Not checking length equality before processing

B. Missing check for reverse mapping from t to s, allowing multiple s chars to map to same t char

C. Using zip instead of indexing causes index errors

D. Returning True prematurely inside the loop

Solution

1. Step 1: Identify missing reverse mapping check

   The code only maps from s to t but does not verify if multiple characters in s map to the same character in t.

2. Step 2: Understand consequences

   This allows incorrect cases like s="ab" and t="aa" to return True incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bidirectional mapping is required to ensure one-to-one mapping [OK]

Hint: Check both s->t and t->s mappings [OK]

Common Mistakes:

• Assuming single-direction mapping suffices
• Ignoring length check
• Misusing zip causing errors

3. What is the time complexity of the optimal hash set approach for finding the longest consecutive sequence in an array of size n?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n) because each number is processed at most twice

C. O(n²) because of nested loops checking consecutive numbers

D. O(n) average but O(n²) worst case due to hash collisions

Solution

1. Step 1: Analyze outer loop

   The outer loop iterates over each unique number once.

2. Step 2: Analyze inner while loop

   Each number is visited at most once in the inner loop when counting consecutive sequences, so total work is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set lookups are O(1), total linear time [OK]

Hint: Each element visited once in sequence counting [OK]

Common Mistakes:

• Assuming sorting is involved causing O(n log n)
• Confusing nested loops as O(n²)
• Overestimating hash collision impact

4. Identify the bug in the following Two Sum implementation using a hash map:

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    seen = {}
    for i, num in enumerate(nums):
        if num in seen:
            return [seen[num], i]
        complement = target - num
        seen[complement] = i

What is the issue?

medium

A. Line 5: Checking if num in seen instead of complement

B. Line 7: Storing complement as key instead of num

C. Line 6: Returning indices in wrong order

D. Line 4: Using a dictionary instead of a list

Solution

1. Step 1: Understand what is stored in the hash map

   The code stores complement as key with current index as value, which is incorrect because we need to store the number itself to check for complements later.

2. Step 2: Identify the bug line

   Line 7 stores complement as key instead of num, causing lookups to fail or return incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash map keys must be numbers seen, not complements [OK]

Hint: Store numbers as keys, not complements, in hash map [OK]

Common Mistakes:

• Storing complements as keys
• Returning indices in wrong order
• Using list instead of dict for lookups

5. Suppose the problem changes: now elements can be reused multiple times, and you want the top k elements by total frequency including duplicates. Which modification to the optimal bucket sort approach correctly handles this?

hard

A. Use the same bucket sort approach since frequencies already count duplicates.

B. Modify frequency counting to count unique elements only, then apply bucket sort.

C. Use a min-heap to track top k elements dynamically as frequencies update with reuse.

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

Solution

1. Step 1: Understand reuse changes frequency dynamics

   Elements can appear multiple times dynamically, so frequencies update continuously.

2. Step 2: Bucket sort is static and cannot handle dynamic frequency updates

   Min-heap allows maintaining top k elements efficiently as frequencies change.

3. Step 3: Choose min-heap approach for dynamic top k tracking

   Min-heap keeps size k and updates with new frequencies, suitable for reuse scenario.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Bucket sort is static; min-heap adapts to frequency changes [OK]

Hint: Dynamic frequency updates require min-heap, not bucket sort [OK]

Common Mistakes:

• Assuming bucket sort works with dynamic reuse
• Counting unique elements only loses frequency info
• Sorting entire array is inefficient