First Non Repeating Character Using Hash in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a hash map to find the first non-repeating character in a string?

Use a hash map to count how many times each character appears, then find the first character with a count of 1.

beginner

Why do we need two passes over the string when using a hash map to find the first non-repeating character?

First pass counts characters, second pass finds the first character with count 1.

beginner

In C++, which standard library container is commonly used as a hash map for character counting?

std::unordered_map is commonly used for fast character counting.

intermediate

What is the time complexity of finding the first non-repeating character using a hash map?

O(n), where n is the length of the string, because we do two passes over the string.

beginner

What should be returned if all characters in the string repeat?

Return a special value like -1 or indicate no non-repeating character found.

What data structure is best to count character frequencies for this problem?

A Stack

B Hash map

C Queue

D Linked list

Hash map allows fast counting of characters by mapping each character to its frequency.

How many times do we scan the string to find the first non-repeating character using a hash map?

A One time

B Four times

C Two times

D Three times

First to count frequencies, second to find the first character with frequency 1.

What is the output if the input string is "aabbcc"?

A -1 (no non-repeating character)

B b

C c

D a

All characters repeat, so no non-repeating character exists.

Which C++ container is NOT suitable for this problem?

A std::unordered_map<char, int>

B std::map<char, int>

C std::vector<int>

D std::stack<char>

Stack does not help count frequencies or find first non-repeating character.

What is the best way to handle characters outside ASCII range in this problem?

A Use a hash map that supports all characters

B Ignore them

C Use an array of size 26

D Use a queue

Hash map can handle any character, including Unicode, unlike fixed-size arrays.

Explain step-by-step how to find the first non-repeating character in a string using a hash map.

Think about counting first, then searching.

Describe the advantages of using a hash map over an array for this problem.

Consider character variety and lookup speed.

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