First Unique Character in a String

+10

You get a string s of lowercase English letters. Find the first character that appears exactly once in the whole string and return its index, counting from 0. If every character appears more than once, return -1.

Function

firstUniqChar(s: string) → integer

sstring: the string to search, lowercase letters only
Returnsinteger: the index of the first letter that appears exactly once, or -1 if there is none

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s contains only lowercase English letters (a to z).

Examples

Input: s = "coddycode"
Output: 4
Explanation: In coddycode the letters c and o appear twice, d three times and e once, at index 8. But y also appears once, at index 4, and it comes first, so the answer is 4.

Input: s = "swiss"
Output: 1
Explanation: In swiss the letter s appears three times. The letter w at index 1 appears once, and so does i at index 2; the first of them wins, so the answer is 1.

Input: s = "aabbcc"
Output: -1
Explanation: Every letter in aabbcc appears twice, so no character is unique and the answer is -1.

+17 hidden tests on Submit

Follow-up

Characters arrive one at a time from a stream, and after each one you must report the first unique character so far. How would you keep the answer up to date?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A letter that looks unique when you reach it can repeat at the very end of the string, so a single left to right glance is not enough. Count every letter first, then the second pass can tell in constant time whether each position holds a unique letter.

Look for a second copy of each letter

Correct, but does not finish on the largest tests

Intuition

Go through the positions from the left. For position i, scan the whole string for another position j with the same letter. If there is none, s[i] is unique, and since you go from the left, it is the first unique letter: return i. In coddycode, positions 0 to 3 each find a copy, and position 4, the y, finds none.

The scan must cover the whole string, before and after i. A copy earlier in the string disqualifies the letter as much as a later one.

Stopping at the first copy helps on most strings, but not all. When each letter sits in one long run, like 2000 as, then 2000 bs and so on, the scan for every letter walks past all the earlier runs before it finds a copy. For n = 5 × 10^4 that is over a billion comparisons, too slow for the largest tests.

Algorithm

For each index i from left to right:
Scan every index j other than i, and stop at the first one where s[j] equals s[i].
If no such j exists, return i.
If every index found a copy, return -1.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

Count letters, then scan

Intuition

The brute force asks "does this letter appear anywhere else?" again for every position. Count once instead. Only 26 letters exist, so an array of 26 counters holds every count, with index 0 for a and index 25 for z. The index of a letter is its character code minus the code of a.

The first pass fills the counters. For coddycode they read c: 2, o: 2, d: 3, y: 1, e: 1. The second pass walks the string from the left and stops at the first position whose letter has a count of 1. That is y at index 4. The second pass has to walk the string, not the 26 counters, because the question is about the first position, not the first letter of the alphabet.

Both passes read the string once, so the time is O(n). The counters stay at 26 however long the string is, so the extra space is O(1).

Algorithm

Create an array of 26 zeros.
For each letter of s, add 1 to its counter.
Walk s again from index 0. Return the first index whose letter has a count of 1.
If the walk ends, return -1.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

Pitfalls and edge cases

Most mistakes come from deciding too early or from walking the wrong thing in the second pass.

Checking only the letters before position i. In abca the first a has no copy before it, yet it is not unique.
Walking the counter array instead of the string in the second pass. For ba, the first counter equal to 1 belongs to a, but the answer is index 0, the b.
Returning the letter instead of its index, or returning the index as 1-based. Lua and R count from 1, so subtract 1 before returning.
Forgetting the -1 case. A string like aabbcc has no unique letter, and the function must still return a value after the loop.
Indexing the counters with the raw character code. a is 97, far past the end of an array of 26; subtract the code of a first.

Frequently asked questions4

What is the time complexity of First Unique Character in a String?

Counting the letters and then scanning the string are two passes of n steps each, so the time is O(n). The 26 counters take the same space for any length, which makes the extra space O(1).

Can you solve it in one pass over the string?

Yes. In one pass, store for each letter the index where it first appeared, or mark it as repeated when it shows up again. Then check the 26 letters and take the smallest index among those that appeared once. The string is read once, and the final check costs 26 steps.

Should you use a hash map or an array to count the letters?

With only lowercase letters, an array of 26 counters is smaller and faster than a hash map. A hash map is the right choice when the string can hold any character, such as Unicode text. The algorithm stays the same: count, then scan the string.

Why does the second pass go over the string and not over the counts?

The counts only say which letters are unique, not where they sit. The answer is the unique letter that comes first in the string, so you have to walk the string in order and stop at the first position whose letter has a count of 1.

Python

def firstUniqChar(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "coddycode"

Expected