First Non Repeating Character Using Hash in DSA C++ - 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

↓

For each char in string

↓

Check if count == 1?

No→Continue

Yes↓

Return this char as first non repeating

↓

If none found, return special char or -1

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

Execution Sample

DSA C++

string s = "swiss";
unordered_map<char,int> count;
for(char c : s) count[c]++;
for(char c : s) if(count[c] == 1) return c;
return -1;

Counts characters in 'swiss' and returns the first non-repeating character.

Execution Table

Step	Operation	Character Processed	Hash Map State	First Non Repeating Candidate	Visual State
1	Initialize hash map	-	{}	-	[]
2	Process char	s	{"s":1}	-	[s]
3	Process char	w	{"s":1,"w":1}	-	[s, w]
4	Process char	i	{"s":1,"w":1,"i":1}	-	[s, w, i]
5	Process char	s	{"s":2,"w":1,"i":1}	-	[s, w, i, s]
6	Process char	s	{"s":3,"w":1,"i":1}	-	[s, w, i, s, s]
7	Check char count	s	{"s":3,"w":1,"i":1}	No (count=3)	[s, w, i, s, s]
8	Check char count	w	{"s":3,"w":1,"i":1}	Yes (count=1)	[s, w, i, s, s]
9	Return first non repeating	-	-	w	[s, w, i, s, s]

💡 Found 'w' with count 1 at step 8, returned as first non repeating character.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 8	Final
count	{}	{"s":1}	{"s":1,"w":1}	{"s":1,"w":1,"i":1}	{"s":2,"w":1,"i":1}	{"s":3,"w":1,"i":1}	{"s":3,"w":1,"i":1}	{"s":3,"w":1,"i":1}
first_non_repeating	-	-	-	-	-	-	w	w

Key Moments - 3 Insights

Why do we need two loops instead of one?

The first loop counts all characters (see steps 2-6), the second loop finds the first character with count 1 (steps 7-9). Doing both in one loop would miss the full counts.

What if no character has count 1?

After checking all characters in the second loop (like steps 7-8), if none has count 1, the function returns -1 (not shown in table but implied after step 9).

Why do we check characters in original string order in second loop?

Because we want the first non repeating character by order of appearance, not just any character with count 1. This is shown in steps 7-9.

Visual Quiz - 3 Questions

Look at the execution table, what is the hash map state after processing the third character?

A {"s":2,"w":1,"i":1}

B {"s":1,"w":1,"i":1}

C {"s":1,"w":2,"i":1}

D {"s":3,"w":1,"i":1}

💡 Hint

Check row with Step 4 in execution_table under 'Hash Map State'

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

A Step 8

B Step 6

C Step 7

D Step 9

💡 Hint

Look at 'First Non Repeating Candidate' column in execution_table rows

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

A 'c'

B 'b'

C -1

D 'a'

💡 Hint

Refer to key_moments about what happens if no character has count 1

Concept Snapshot

Use a hash map to count characters.
Loop over string to fill counts.
Loop again to find first char with count 1.
Return that char or -1 if none.
Two passes ensure correct order and counts.

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 to find the first character whose count is exactly one. If found, it returns that character; otherwise, it returns -1. This two-step process ensures we know the frequency of all characters before deciding which is first non repeating.

Practice

1. What is the main purpose of using a hash map in finding the first non-repeating character in a string?

easy

A. To reverse the string efficiently

B. To sort the characters alphabetically

C. To store characters in a linked list

D. To store the frequency of each character for quick lookup

Solution

1. Step 1: Understand the role of hash map

   A hash map stores each character as a key and its frequency as the value, allowing quick frequency lookup.

2. Step 2: Why frequency is important

   Knowing frequency helps identify which character appears only once, which is the first non-repeating character.

3. Final Answer:

   To store the frequency of each character for quick lookup -> Option D

4. Quick Check:

   Hash map = frequency storage [OK]

Hint: Hash map counts characters fast for first unique [OK]

Common Mistakes:

• Thinking hash map sorts characters
• Using hash map to reverse string
• Confusing hash map with linked list

2. Which of the following C++ code snippets correctly declares a hash map to store character frequencies?

easy

A. std::unordered_map freq;

B. std::map freq;

C. std::unordered_map freq;

D. std::vector<int> freq(26);

Solution

1. Step 1: Identify correct hash map declaration

   We need a map with character keys and integer values for frequency, so std::unordered_map is correct.

2. Step 2: Why others are incorrect

   std::map freq; reverses key and value types; std::vector<int> freq(26); uses vector, not a hash map; std::unordered_map freq; uses string keys, not char.

3. Final Answer:

   std::unordered_map<char, int> freq; -> Option C

4. Quick Check:

   Correct map type = unordered_map<char, int> [OK]

Hint: Use unordered_map for char frequency [OK]

Common Mistakes:

• Using map with wrong key-value types
• Using vector instead of map
• Using string keys instead of char

3. What will be the output of the following C++ code snippet?

std::string s = "swiss";
std::unordered_map freq;
for (char c : s) freq[c]++;
for (char c : s) {
  if (freq[c] == 1) {
    std::cout << c << std::endl;
    break;
  }
}

medium

A. s

B. w

C. i

D. No output

Solution

1. Step 1: Count character frequencies

   Characters: s(3), w(1), i(1). Frequencies: s=3, w=1, i=1.

2. Step 2: Find first character with frequency 1

   Iterate string: 's'(3), 'w'(1) -> first non-repeating is 'w'.

3. Final Answer:

   w -> Option B

4. Quick Check:

   First unique char = w [OK]

Hint: Check frequencies, print first with count 1 [OK]

Common Mistakes:

• Printing first character without checking frequency
• Confusing 'i' as first unique
• Ignoring frequency counts

4. Identify the error in the following code snippet that attempts to find the first non-repeating character:

std::string s = "hello";
std::unordered_map freq;
for (int i = 0; i <= s.size(); i++) {
  freq[s[i]]++;
}
for (int i = 0; i < s.size(); i++) {
  if (freq[s[i]] == 1) {
    std::cout << s[i] << std::endl;
    break;
  }
}

medium

A. Loop condition should be i < s.size(), not i <= s.size()

B. Frequency map should use string keys, not char

C. The break statement is missing

D. The output should be stored in a variable, not printed

Solution

1. Step 1: Check loop boundary in frequency count

   The loop uses i <= s.size(), which accesses s[s.size()] out of bounds causing undefined behavior.

2. Step 2: Correct loop boundary

   Change condition to i < s.size() to avoid out-of-range access.

3. Final Answer:

   Loop condition should be i < s.size(), not i <= s.size() -> Option A

4. Quick Check:

   Loop boundary off by one error [OK]

Hint: Use i < size(), not <= size() in loops [OK]

Common Mistakes:

• Using <= instead of < in loops
• Confusing char and string keys
• Thinking break is missing

5. Given the string "aabbccdde", which modification to the standard hash map approach will correctly find the first non-repeating character when some characters appear multiple times and others only once at the end?

hard

A. Store character frequencies and track insertion order using a queue

B. Sort the string before counting frequencies

C. Use a vector instead of a hash map for frequency

D. Only count characters until the first repeating character

Solution

1. Step 1: Understand problem with standard hash map

   Hash map stores frequencies but does not keep order, so first unique character position is lost.

2. Step 2: Use queue to track order

   By storing characters in a queue as they appear, and checking frequency, we can find the first non-repeating character in order.

3. Final Answer:

   Store character frequencies and track insertion order using a queue -> Option A

4. Quick Check:

   Frequency + order tracking = correct first unique [OK]

Hint: Track order with queue alongside frequency map [OK]

Common Mistakes:

• Sorting string loses original order
• Using vector loses quick lookup
• Stopping count too early