First Non Repeating Character Using Hash in DSA Python - Execution Trace

Concept Flow - First Non Repeating Character Using Hash

Start with input string

↓

Create empty hash map for counts

↓

For each char in string

↓

Increment char count in hash map

↓

For each char in string

↓

Check if char count is 1?

No→Continue

Yes↓

Return this char as first non repeating

↓

If none found, return None or -1

Count characters using a hash map, then find the first character with count 1.

Execution Sample

DSA Python

def first_non_repeating_char(s):
    counts = {}
    for c in s:
        counts[c] = counts.get(c, 0) + 1
    for c in s:
        if counts[c] == 1:
            return c
    return None

This code finds the first character in the string that appears only once.

Execution Table

Step	Operation	Character Processed	Hash Map State	Check Condition	Result / Action
1	Initialize hash map	-	{}	-	Empty hash map created
2	Count char	a	{"a":1}	-	Count 'a' as 1
3	Count char	b	{"a":1, "b":1}	-	Count 'b' as 1
4	Count char	c	{"a":1, "b":1, "c":1}	-	Count 'c' as 1
5	Count char	a	{"a":2, "b":1, "c":1}	-	Increment 'a' count to 2
6	Count char	b	{"a":2, "b":2, "c":1}	-	Increment 'b' count to 2
7	Count char	d	{"a":2, "b":2, "c":1, "d":1}	-	Count 'd' as 1
8	Check first non repeating	a	{"a":2, "b":2, "c":1, "d":1}	counts['a'] == 1?	No, count is 2, continue
9	Check first non repeating	b	{"a":2, "b":2, "c":1, "d":1}	counts['b'] == 1?	No, count is 2, continue
10	Check first non repeating	c	{"a":2, "b":2, "c":1, "d":1}	counts['c'] == 1?	Yes, count is 1, return 'c'
11	Return result	-	-	-	First non repeating character is 'c'

💡 Found first character with count 1 at step 10, returned 'c'

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 10	Final
counts	{}	{"a":1}	{"a":1, "b":1}	{"a":1, "b":1, "c":1}	{"a":2, "b":1, "c":1}	{"a":2, "b":2, "c":1}	{"a":2, "b":2, "c":1, "d":1}	{"a":2, "b":2, "c":1, "d":1}	{"a":2, "b":2, "c":1, "d":1}
current_char	-	a	b	c	a	b	d	c	c
result	None	None	None	None	None	None	None	c	c

Key Moments - 3 Insights

Why do we need two loops instead of one?

The first loop counts all characters, building the hash map (see steps 2-7). The second loop checks the original order to find the first character with count 1 (steps 8-10). Doing both in one loop would miss order.

What if no character has count 1?

If no character count is 1, the second loop finishes without returning (not shown in table). Then the function returns None (step 11). This means no non repeating character exists.

Why do we check counts[c] == 1 and not counts[c] > 0?

We want the first character that appears exactly once. Counts greater than 1 mean repeating characters, so we skip those (see steps 8-9).

Visual Quiz - 3 Questions

Look at the execution table, what is the hash map state after processing character 'b' the second time?

A {"a":2, "b":2, "c":1}

B {"a":1, "b":2, "c":1}

C {"a":2, "b":1, "c":1}

D {"a":2, "b":2, "c":2}

💡 Hint

Check step 6 in the execution table where 'b' is processed the second time.

At which step does the function find the first non repeating character?

A Step 9

B Step 10

C Step 8

D Step 11

💡 Hint

Look at the 'Check first non repeating' operations and when the condition counts[c] == 1 is true.

If the input string was 'aabbcc', what would the function return?

A 'a'

B 'b'

C None

D 'c'

💡 Hint

Refer to the key moments about what happens if no character has count 1.

Concept Snapshot

Use a hash map to count characters.
First loop: count all characters.
Second loop: find first char with count 1.
Return that char or None if none found.
Preserves original order.
Simple and efficient approach.

Full Transcript

This concept finds the first non repeating character in a string using a hash map. First, it counts how many times each character appears by looping through the string once. Then, it loops again through the string in original order to find the first character whose count is exactly one. If found, it returns that character; otherwise, it returns None. This method ensures the order is preserved and is efficient because it uses hashing for counting.