LeetCode: 387. First Unique Character in a String

2026-02-28

We can optimize even the complexity order is the same. Reduce twice loop to once.

387. First Unique Character in a String

LeetCode: 387. First Unique Character in a String

Summary

Find the index of the first unique character in the given string. If it does not exist, return -1.

Approach

Use a simple two-pass approach: count each character occurrence with a hash map, then find the smallest index whose count is 1.

Function

Initialization:

  • indices_map: key is the character, value is the list of indices.

Main loop 1: Counting

  • For each character, append its index to indices_map[ch].

Main loop 2: Find answer

  • Set best_idx = len(s) + 1 (sentinel).
  • For each key in indices_map:
  • If len(indices_map[key]) == 1, update best_idx = min(best_idx, indices_map[key][0]).

Finally, return best_idx if best_idx <= len(s) - 1, otherwise -1.

Complexity

Time Complexity: O(N), where N is the length of the string. Space Complexity: O(N). The hash map stores characters and their indices.

Optimization

We traverse the string and hash map twice. We can reduce this to one pass.

Approach

Use a dictionary and rely on Python dict insertion order.

Function

Initialization:

  • indices: key is the character and value is its first index.
  • seen: set of characters we have already seen.

Main loop:

  • For each character ch at index i in s
    • If ch is in seen and also in indices, delete ch from indices.
    • Else, set indices[ch] = i.
    • Add ch to seen.

Return the first value in indices if it is not empty; otherwise return -1. You can extract it with next(iter(indices.values())) in O(1) extra space.

Complexity

Time Complexity: O(N). It is the same as the first solution, but it uses one pass. Space Complexity: O(1) if the input is limited to lowercase English letters; otherwise O(N) in the general case.