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

Concept Flow - First Non Repeating Character Using Hash

Start

↓

Create empty hash map

↓

Traverse string: For each char

↓

Increment char count in hash

↓

Traverse string again

↓

Check hash count of char

↓

Return char

↓

If none found, return -1

↓

End

We count each character's frequency using a hash map, then find the first character with count 1.

Execution Sample

DSA C

char str[] = "swiss";
int hash[256] = {0};
for (int i=0; str[i]; i++) hash[(unsigned char)str[i]]++;
for (int i=0; str[i]; i++) if (hash[(unsigned char)str[i]] == 1) return i;
return -1;

Counts characters in 'swiss' then finds first non-repeating character index.

Execution Table

Step	Operation	Character Processed	Hash Count Update	Current Hash State (partial)	Action	Result
1	Initialize hash map	-	All zero	All zeros	Start counting	-
2	Count 's'	's'	hash['s'] = 1	{'s':1}	Continue counting	-
3	Count 'w'	'w'	hash['w'] = 1	{'s':1, 'w':1}	Continue counting	-
4	Count 'i'	'i'	hash['i'] = 1	{'s':1, 'w':1, 'i':1}	Continue counting	-
5	Count 's'	's'	hash['s'] = 2	{'s':2, 'w':1, 'i':1}	Continue counting	-
6	Count 's'	's'	hash['s'] = 3	{'s':3, 'w':1, 'i':1}	Counting done	-
7	Check first char 's'	's'	hash['s'] = 3	{'s':3, 'w':1, 'i':1}	Count > 1, skip	-
8	Check second char 'w'	'w'	hash['w'] = 1	{'s':3, 'w':1, 'i':1}	Count == 1, return index 1	Index 1
9	End	-	-	-	-	First non-repeating char index = 1

💡 Found first character with count 1 at index 1 ('w'), stop.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
hash['s']	0	1	1	1	2	3	3	3	3
hash['w']	0	0	1	1	1	1	1	1	1
hash['i']	0	0	0	1	1	1	1	1	1
i (index)	0	0	0	0	0	0	1	1	1

Key Moments - 3 Insights

Why do we need two passes over the string?

The first pass counts all characters (see steps 2-6), the second pass finds the first with count 1 (steps 7-8). We can't find the first non-repeating character in one pass because counts are unknown initially.

Why do we use a hash map with size 256?

Because we assume ASCII characters, each character maps to an index 0-255 in the hash array to count frequency efficiently (shown in variable_tracker).

What if no non-repeating character exists?

If no character has count 1 after second pass, the function returns -1 (not shown in this example but implied after step 9).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the count of 's' in the hash?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Hash Count Update' and 'Current Hash State' columns at step 6.

At which step does the algorithm find the first non-repeating character?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look at the 'Action' and 'Result' columns in the execution_table.

If the input string was "aabbcc", what would the final result be?

A Index 0

B Index 1

C -1

D Index 2

💡 Hint

No character appears once, so the function returns -1 as per the exit_note.

Concept Snapshot

First Non Repeating Character Using Hash
- Use a hash map (array) to count character frequencies
- First pass: count all chars
- Second pass: find first char with count 1
- Return index or -1 if none
- Works in O(n) time with O(1) space for ASCII

Full Transcript

This concept finds the first character in a string that does not repeat. It uses a hash map to count how many times each character appears. First, it goes through the string and counts each character. Then, it goes through the string again to find the first character with count one. If found, it returns the index of that character. Otherwise, it returns -1. This method is efficient and works well for ASCII characters.