First Unique Character in a String

▶

Steps

setup

Initialize frequency and first_index maps

Create empty hash maps to store character frequencies and their first occurrence indices before processing the string.

💡 Initializing these maps is essential to track counts and positions as we iterate through the string.

Line:

freq = {}
first_index = {}

💡 Starting with empty maps sets the foundation for counting and indexing characters.

fill_row

Process character 'l' at index 0

Encounter 'l' at index 0: increment its frequency to 1 and record its first occurrence index as 0.

💡 The first time we see 'l', we add it to both maps with count 1 and index 0.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 New characters get their first index recorded immediately, ensuring we know where they first appeared.

fill_row

Process character 'e' at index 1

Encounter 'e' at index 1: increment frequency to 1 and record first occurrence index as 1.

💡 Like 'l', 'e' is new, so we add it to both maps with count 1 and index 1.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 Each new character is tracked with its first index to identify uniqueness later.

fill_row

Process character 'e' at index 2

Encounter 'e' again at index 2: increment its frequency from 1 to 2; first index remains 1.

💡 Since 'e' is already in first_index, we only update its frequency count.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 Repeated characters increase frequency but keep their original first index.

fill_row

Process character 't' at index 3

Encounter 't' at index 3: add it with frequency 1 and record first occurrence index 3.

💡 New character 't' is added to both maps with count 1 and index 3.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 Tracking new characters ensures we can identify unique ones later.

fill_row

Process character 'c' at index 4

Encounter 'c' at index 4: add it with frequency 1 and record first occurrence index 4.

💡 New character 'c' is added to both maps with count 1 and index 4.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 Each new character is tracked for frequency and first index.

fill_row

Process character 'o' at index 5

Encounter 'o' at index 5: add it with frequency 1 and record first occurrence index 5.

💡 New character 'o' is added to both maps with count 1 and index 5.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 Tracking all characters ensures we can find unique ones later.

fill_row

Process character 'd' at index 6

Encounter 'd' at index 6: add it with frequency 1 and record first occurrence index 6.

💡 New character 'd' is added to both maps with count 1 and index 6.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 All characters are tracked to find the first unique one.

fill_row

Process character 'e' at index 7

Encounter 'e' again at index 7: increment its frequency from 2 to 3; first index remains 1.

💡 Repeated character 'e' frequency increases, no index update.

Line:

freq[ch] = freq.get(ch, 0) + 1
if ch not in first_index:
    first_index[ch] = i

💡 Frequency updates reflect repeated characters, confirming 'e' is not unique.

setup

Initialize min_index to string length

Set min_index to length of string (8) to find the smallest index of unique characters.

💡 Starting min_index at max ensures any unique character index found will be smaller.

Line:

min_index = len(s)

💡 This variable will track the earliest unique character index.

compare

Check character 'l' with frequency 1

Check if 'l' is unique (frequency 1) and if its first index 0 is less than min_index (8). Update min_index to 0.

💡 Finding a unique character with a smaller index updates min_index to track earliest unique character.

Line:

if count == 1 and first_index[ch] < min_index:
    min_index = first_index[ch]

💡 'l' is currently the earliest unique character found.

compare

Check character 'e' with frequency 3

Check if 'e' is unique (frequency 3). It is not, so min_index remains 0.

💡 Characters with frequency > 1 are not unique and do not update min_index.

Line:

if count == 1 and first_index[ch] < min_index:
    min_index = first_index[ch]

💡 'e' is not unique, so it is skipped.

compare

Check character 't' with frequency 1

Check if 't' is unique (frequency 1) and if its first index 3 is less than min_index (0). It is not, so min_index remains 0.

💡 Unique characters with index greater than current min_index do not update min_index.

Line:

if count == 1 and first_index[ch] < min_index:
    min_index = first_index[ch]

💡 't' is unique but appears after 'l', so 'l' remains earliest.

compare

Check character 'c' with frequency 1

Check if 'c' is unique (frequency 1) and if its first index 4 is less than min_index (0). It is not, so min_index remains 0.

💡 Unique characters with index greater than min_index do not update min_index.

Line:

if count == 1 and first_index[ch] < min_index:
    min_index = first_index[ch]

💡 'c' is unique but appears after 'l', so 'l' remains earliest.

compare

Check character 'o' with frequency 1

Check if 'o' is unique (frequency 1) and if its first index 5 is less than min_index (0). It is not, so min_index remains 0.

💡 Unique characters with index greater than min_index do not update min_index.

Line:

if count == 1 and first_index[ch] < min_index:
    min_index = first_index[ch]

💡 'o' is unique but appears after 'l', so 'l' remains earliest.

compare

Check character 'd' with frequency 1

Check if 'd' is unique (frequency 1) and if its first index 6 is less than min_index (0). It is not, so min_index remains 0.

💡 Unique characters with index greater than min_index do not update min_index.

Line:

if count == 1 and first_index[ch] < min_index:
    min_index = first_index[ch]

💡 'd' is unique but appears after 'l', so 'l' remains earliest.

reconstruct

Return the earliest unique character index

Since min_index is 0 (less than string length), return 0 as the index of the first unique character.

💡 Returning min_index gives the position of the first unique character in the string.

Line:

return min_index if min_index != len(s) else -1

💡 The algorithm successfully identified 'l' at index 0 as the first unique character.

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

if __name__ == '__main__':
    print(firstUniqChar('leetcode'))  # 0

📊

First Unique Character in a String - Watch the Algorithm Execute, Step by Step

Watching each update to the frequency and index maps reveals how the algorithm efficiently identifies unique characters in a single pass, which is hard to grasp by reading code alone.

insert

empty map

insert

Lookup: l

l→1lookup

insert

Lookup: e

l→1

e→1lookup

increment

Lookup: e→ 1

l→1

e→2lookup

insert

Lookup: t

l→1

e→2

t→1lookup

insert

Lookup: c

l→1

e→2

t→1

c→1lookup

insert

Lookup: o

l→1

e→2

t→1

c→1

o→1lookup

insert

Lookup: d

l→1

e→2

t→1

c→1

o→1

d→1lookup

increment

Lookup: e→ 2

l→1

e→3lookup

t→1

c→1

o→1

d→1

check

l→1

e→3

t→1

c→1

o→1

d→1

Result: 8

check

Lookup: l→ 1

l→1lookup

Result: 0

check

Lookup: e→ 3

e→3lookup

Result: 0

check

Lookup: t→ 1

t→1lookup

Result: 0

check

Lookup: c→ 1

c→1lookup

Result: 0

check

Lookup: o→ 1

o→1lookup

Result: 0

check

Lookup: d→ 1

d→1lookup

Result: 0

lookup

l→1

e→3

t→1

c→1

o→1

d→1

Result: 0

Key Takeaways

✓ Tracking both frequency and first occurrence index in a single pass enables efficient identification of the first unique character.

This insight is difficult to see from code alone because it requires understanding how two maps work together to solve the problem.

✓ Incrementing frequency counts while preserving first indices ensures repeated characters are correctly identified as non-unique.

Visualizing frequency updates clarifies why only characters with count 1 are candidates for uniqueness.

✓ Comparing first indices of unique characters to find the minimum reveals how the algorithm selects the earliest unique character.

Seeing min_index update step-by-step shows the decision process behind returning the correct index.

Practice

1. You are given an integer array and a number k. You need to find the length of the longest contiguous subarray whose sum is divisible by k. Which of the following approaches guarantees an optimal solution in O(n) time?

easy

A. Use a nested loop to check all subarrays and verify divisibility by k.

B. Use dynamic programming to store the maximum length subarray ending at each index with sum divisible by k.

C. Use a sliding window that expands and contracts based on the current sum modulo k.

D. Use prefix sums and a hash map to store the earliest index of each remainder modulo k.

Solution

1. Step 1: Understand the problem constraints

   We want the longest subarray with sum divisible by k. Checking all subarrays with nested loops is O(n^2) and inefficient.

2. Step 2: Recognize prefix sum + remainder pattern

   Using prefix sums modulo k, if two prefix sums have the same remainder, the subarray between them is divisible by k. Storing earliest indices of remainders in a hash map allows O(n) solution.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + hash map is classic for subarray sum modulo problems [OK]

Hint: Prefix sums + remainder hash map -> O(n) solution [OK]

Common Mistakes:

• Thinking sliding window works for modulo sums
• Assuming DP is needed for this problem
• Believing brute force is acceptable for large inputs

2. What is the time complexity of the optimal prefix sum + hash map solution for checking if a continuous subarray sum is a multiple of k, given an input array of length n and integer k?

medium

A. O(n * k)

B. O(n^2)

C. O(n)

D. O(k)

Solution

1. Step 1: Analyze the main loop over n elements

   The algorithm iterates once over the array, performing O(1) operations per element.

2. Step 2: Consider hash map operations and modulo computations

   Hash map lookups and insertions are average O(1), modulo operations are O(1), so total is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming modulo k affects complexity multiplicatively
• Thinking hash map size depends on k linearly

3. What is the time complexity of the optimal character frequency counting approach for grouping anagrams, given n strings each of length k?

medium

A. O(n * k log k)

B. O(n^2 * k log k)

C. O(n * k)

D. O(n * k^2)

Solution

1. Step 1: Identify loops in the algorithm

   Outer loop runs n times, inner loop counts characters in each string of length k.

2. Step 2: Analyze operations inside loops

   Counting frequency is O(k), creating tuple key is O(26) constant, appending to map is O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(n * k) [OK]

Hint: Frequency counting is linear in string length [OK]

Common Mistakes:

• Confusing sorting cost with counting
• Assuming k log k due to sorting
• Mistaking quadratic complexity

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

5. The following code attempts to find the longest subarray with sum divisible by k. Identify the line containing the subtle bug that causes incorrect results for arrays containing negative numbers.

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k
    earliest[0] = -1
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        # Bug: missing adjustment for negative remainder
        if earliest[remainder] != -2:
            max_length = max(max_length, i - earliest[remainder])
        else:
            earliest[remainder] = i
    return max_length

medium

A. Line computing remainder = prefix_sum % k

B. Line initializing earliest[0] = -1

C. Line updating max_length = max(max_length, i - earliest[remainder])

D. Line setting earliest[remainder] = i

Solution

1. Step 1: Identify remainder calculation

   When prefix_sum is negative, prefix_sum % k in Python returns a non-negative remainder, but in some languages or implementations it can be negative. The code lacks adjustment for negative remainder.

2. Step 2: Why this causes bugs

   If remainder is negative, indexing earliest array causes errors or misses correct subarrays. The fix is to add if remainder < 0: remainder += k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Negative prefix sums require remainder adjustment [OK]

Hint: Check remainder calculation for negative sums [OK]

Common Mistakes:

• Forgetting to adjust negative remainders
• Misinitializing earliest array
• Updating max_length incorrectly