First Non Repeating Character Using Hash in DSA Python

Mental Model

We count how many times each letter appears, then find the first letter that appears only once.

Analogy: Imagine a classroom where each student raises their hand once. We want to find the first student who raised their hand only one time.

string: h -> e -> l -> l -> o -> null
counts: {h:1, e:1, l:2, o:1}
↑ first unique char pointer

Dry Run Walkthrough

Input: string: "swiss"

Goal: Find the first character that appears only once in the string

Step 1: Count characters: s=1

counts = {s:1}

Why: Start counting the first character

Step 2: Count characters: w=1

counts = {s:1, w:1}

Why: Add new character with count 1

Step 3: Count characters: i=1

counts = {s:1, w:1, i:1}

Why: Add new character with count 1

Step 4: Count characters: s=2

counts = {s:2, w:1, i:1}

Why: Increment count for repeated character

Step 5: Count characters: s=3

counts = {s:3, w:1, i:1}

Why: Increment count for repeated character

Step 6: Check characters in order: s count=3 (skip)

string: s -> w -> i -> s -> s -> null

Why: s repeats, so skip

Step 7: Check characters in order: w count=1 (found)

string: s -> w -> i -> s -> s -> null
↑ first unique char at w

Why: w appears only once, so it is the first non repeating character

Result:

string: s -> w -> i -> s -> s -> null
first non repeating character: w

Annotated Code

DSA Python

class Solution:
    def first_non_repeating_char(self, s: str) -> str:
        counts = {}
        # Count each character's frequency
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1
        # Find first character with count 1
        for ch in s:
            if counts[ch] == 1:
                return ch
        return ''  # no non repeating character found

if __name__ == '__main__':
    s = "swiss"
    sol = Solution()
    result = sol.first_non_repeating_char(s)
    print(f"First non repeating character: {result}")

counts[ch] = counts.get(ch, 0) + 1

increment count for each character to track frequency

for ch in s:

iterate characters in original order to find first unique

if counts[ch] == 1:

check if character appears only once

return ch

return first non repeating character immediately

Output

First non repeating character: w

Complexity Analysis

Time: O(n) because we scan the string twice: once to count and once to find the first unique character

Space: O(k) where k is number of unique characters, because we store counts in a hash map

vs Alternative: Compared to checking each character by scanning the whole string repeatedly (O(n^2)), using a hash map is much faster and efficient

Edge Cases

empty string

returns empty string since no characters exist

DSA Python

return ''  # no non repeating character found

all characters repeating

returns empty string because no unique character found

DSA Python

return ''  # no non repeating character found

string with one character

returns that character as it is unique

DSA Python

if counts[ch] == 1:

When to Use This Pattern

When you need to find the first unique element in a sequence, use a hash map to count frequencies and then scan to find the first with count one.

Common Mistakes

Mistake: Checking character uniqueness by scanning the whole string inside a loop, causing O(n^2) time
Fix: Use a hash map to count frequencies first, then scan once to find the first unique character

Mistake: Returning the first character with count 1 without preserving original order
Fix: Iterate over the original string order to find the first unique character

Summary

Finds the first character in a string that does not repeat using a hash map to count frequencies.

Use when you need to quickly identify the first unique character in a string or sequence.

Count all characters first, then scan in original order to find the first with count one.