LeetCode 387: First Unique Character in a String

Problem Restatement

We are given a string s.

We need to find the first character that appears exactly once in the string and return its index.

If every character appears more than once, return -1.

The string contains only lowercase English letters, and its length can be up to 10^5.

Input and Output

Example function shape:

def firstUniqChar(s: str) -> int:
    ...

Examples

Example 1:

s = "leetcode"

Character counts:

The first character with count 1 is l at index 0.

So the answer is:

0

Example 2:

s = "loveleetcode"

The first unique character is v.

It appears at index 2.

So the answer is:

2

Example 3:

s = "aabb"

Every character repeats.

So the answer is:

-1

First Thought: Check Each Character Against the Whole String

A direct method is to examine each character and count how many times it appears.

For each index i, scan the whole string and count s[i].

If the count is 1, return i.

Code shape:

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for i in range(len(s)):
            count = 0

            for ch in s:
                if ch == s[i]:
                    count += 1

            if count == 1:
                return i

        return -1

This is correct, but it is too slow.

For a string of length n, this scans the string once for every character.

That gives O(n^2) time.

With n up to 10^5, this is not acceptable.

Key Insight

We need two pieces of information:

1. How many times each character appears.
2. Which unique character appears first in the original order.

Counting first solves the first part.

Scanning again from left to right solves the second part.

Because the string contains only lowercase English letters, we can use a fixed array of length 26.

Algorithm

Create an array:

count = [0] * 26

First pass:

1. Scan every character in s.
2. Convert the character to an index from 0 to 25.
3. Increment its frequency.

Second pass:

1. Scan s from left to right.
2. For each character, check its frequency.
3. Return the first index whose character count is 1.

If no such index exists, return -1.

Correctness

After the first pass, count stores the exact number of times each lowercase letter appears in s.

During the second pass, we inspect characters in increasing index order.

If count[idx] == 1, then the current character appears exactly once in the whole string. Since we scan from left to right, this is the first such character, so returning its index is correct.

If count[idx] > 1, the current character repeats, so it cannot be the answer.

If the second pass finishes without finding a character with count 1, then no character appears exactly once. Returning -1 is correct.

Complexity

Let n = len(s).

Implementation

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = [0] * 26

        for ch in s:
            idx = ord(ch) - ord("a")
            count[idx] += 1

        for i, ch in enumerate(s):
            idx = ord(ch) - ord("a")

            if count[idx] == 1:
                return i

        return -1

Code Explanation

Create a fixed frequency table:

count = [0] * 26

Count every character:

for ch in s:
    idx = ord(ch) - ord("a")
    count[idx] += 1

The expression:

ord(ch) - ord("a")

maps lowercase letters to array indices:

'a' -> 0
'b' -> 1
...
'z' -> 25

Then scan the string again:

for i, ch in enumerate(s):

The first time we find a character with count 1, return its index:

if count[idx] == 1:
    return i

If there is no unique character:

return -1

Testing

def test_solution():
    s = Solution()

    assert s.firstUniqChar("leetcode") == 0
    assert s.firstUniqChar("loveleetcode") == 2
    assert s.firstUniqChar("aabb") == -1
    assert s.firstUniqChar("z") == 0
    assert s.firstUniqChar("zz") == -1
    assert s.firstUniqChar("aabbc") == 4
    assert s.firstUniqChar("aabbcd") == 4

    print("all tests passed")

test_solution()

Test meaning: