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, c and o appear twice and d three times. Both y (index 4) and e (index 8) appear once, and y comes first, so the answer is 4.

Input: s = "swiss"
Output: 1
Explanation: The letter s appears three times. Both w at index 1 and i at index 2 appear once, and w comes first.

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

Follow-up

Characters arrive one at a time from a stream. How would you report the first unique character so far after each one?

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

For each position from the left, scan the whole string for another position with the same letter. Scan both sides: an earlier copy disqualifies a letter as much as a later one. The first position with no copy is the answer. In coddycode, positions 0 to 3 each find a copy and the y at index 4 finds none.

Stopping at the first copy does not help when each letter sits in one long run, like 2000 as, then 2000 bs and so on: every scan walks past all the earlier runs. At n = 5 × 10^4 that is over a billion comparisons.

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

Count each letter once instead of searching again for every position. Only 26 letters exist, so 26 counters hold every count, indexed by the letter's code minus the code of a.

The first pass fills the counters; for coddycode, only y and e end at 1. The second pass walks the string from the left and stops at the first letter whose count is 1, the y at index 4. Two passes of n steps give O(n) time, and 26 counters are O(1) space for any length.

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

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.
Indexing the counters with the raw character code. a is 97, far past the end of 26 counters.
Returning the letter instead of its index, or a 1-based index in Lua or R.

Frequently asked questions3

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, so the time is O(n). The 26 counters take the same space for any length, so the extra space is 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 repeated when it shows up again. Then take the smallest index among the 26 letters 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. 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.

def firstUniqChar(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Expected Output