First Non Repeating Character Using Hash in DSA C++ - Build from Scratch

First Non Repeating Character Using Hash

📖 Scenario: Imagine you are building a text editor feature that highlights the first character in a sentence that does not repeat anywhere else. This helps users quickly spot unique characters.

🎯 Goal: You will write a program to find the first non-repeating character in a given string using a hash map (dictionary) to count character occurrences.

📋 What You'll Learn

Create a string variable with a specific sentence

Create a hash map (unordered_map) to count characters

Use a loop to fill the hash map with character counts

Use another loop to find the first character with count 1

Print the first non-repeating character or a message if none found

💡 Why This Matters

🌍 Real World

Finding unique characters quickly is useful in text processing, spell checking, and data validation.

💼 Career

Understanding hash maps and string processing is essential for software developers working on text editors, search engines, and data analysis tools.

1

Create the input string

Create a string variable called sentence and set it to "swiss".

DSA C++

# Your code here

Hint

Use std::string to create the variable sentence.

2

Create a hash map to count characters

Include the header <unordered_map> and create an unordered_map<char, int> called charCount to store character counts.

DSA C++

#include 
#include 
#include 

int main() {
    std::string sentence = "swiss";
    std::unordered_map charCount;
    // Your code here
    return 0;
}

Hint

Use #include <unordered_map> and declare charCount as unordered_map<char, int>.

3

Count characters in the string

Use a for loop with variable ch to iterate over sentence and increment charCount[ch] by 1 inside the loop.

DSA C++

#include 
#include 
#include 

int main() {
    std::string sentence = "swiss";
    std::unordered_map charCount;
    // Your code here
    return 0;
}

Hint

Use a range-based for loop to count each character.

4

Find and print the first non-repeating character

Use a for loop with variable ch to iterate over sentence. Inside the loop, check if charCount[ch] == 1. If yes, print ch and break the loop. If no such character is found, print "No non-repeating character found".

DSA C++

#include 
#include 
#include 

int main() {
    std::string sentence = "swiss";
    std::unordered_map charCount;
    for (char ch : sentence) {
        charCount[ch]++;
    }
    // Your code here
    return 0;
}

Hint

Loop again through sentence to find the first character with count 1 and print it. Use a flag to check if found.

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