EasyHash TableStringCounting

First Unique Character in a String

1 approach, code in every language

Given a string, scan it from left to right and find the earliest character that appears exactly once across the whole string. Report the zero-based index of that character.

If every character in the string repeats, no such character exists and you should return -1.

Example 1

Input: s = "swiss"

Output: 1

's' occurs three times, so it is skipped. 'w' at index 1 is the first character that shows up only once.

Example 2

Input: s = "aabbcc"

Output: -1

Every character appears twice, so there is no character that occurs exactly once.

Constraints

1 <= s.length <= 10^5
s contains only lowercase English letters

Count Frequencies, Then Scan

Tally how often each character appears, then walk the string again and return the index of the first character with a count of one.

Loading animation…

Intuition

Uniqueness is a global property: you cannot know a character is unique until you have seen the entire string. So make one pass to record the frequency of every character in a map, then make a second pass in the original order. The first position whose character has a recorded frequency of one is the answer, because scanning left to right guarantees you hit the earliest such index first.

Algorithm walkthrough

1Initialize a frequency table for the characters.
2Traverse the string once, incrementing the count for each character.
3Traverse the string a second time from the start.
4Return the index of the first character whose stored count equals one.
5If the second pass finds none, return -1.

Implementation

class Solution:
    def firstUniqChar(self, s: str) -> int:
        counts = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1
        for i, ch in enumerate(s):
            if counts[ch] == 1:
                return i
        return -1

Time

O(n)

Space

O(1)

Two linear passes over the string; the count table is bounded by the fixed alphabet of 26 letters.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

First Solo Stop is our own problem on the technique behind First Unique Character in a String: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free