First Non Repeating Character Using Hash in DSA C++

Mental Model

We want to find the first letter in a word that appears only once by counting how many times each letter shows up.

Analogy: Imagine a classroom where each student raises their hand once. We want to find the first student who raised their hand only once, ignoring those who raised it multiple times.

word: h -> e -> l -> l -> o -> null
hash: {h:1, e:1, l:2, o:1}
↑ first unique character pointer

Dry Run Walkthrough

Input: string: "hello"

Goal: Find the first character that appears only once in the string

Step 1: Count frequency of each character in the string

hash: {h:1, e:1, l:2, o:1}

Why: We need to know how many times each character appears to identify unique ones

Step 2: Check characters in order to find the first with frequency 1

checking 'h' -> frequency 1

Why: The first character with count 1 is the answer

Step 3: Return 'h' as the first non repeating character

result: 'h'

Why: We found the first unique character

Result:

h

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

char firstNonRepeatingChar(const string& s) {
    unordered_map<char, int> freq;
    // Count frequency of each character
    for (char c : s) {
        freq[c]++;
    }
    // Find first character with frequency 1
    for (char c : s) {
        if (freq[c] == 1) {
            return c;
        }
    }
    return '\0'; // Return null char if none found
}

int main() {
    string input = "hello";
    char result = firstNonRepeatingChar(input);
    if (result != '\0') {
        cout << result << endl;
    } else {
        cout << "No unique character" << endl;
    }
    return 0;
}

for (char c : s) { freq[c]++; }

Count how many times each character appears

for (char c : s) { if (freq[c] == 1) { return c; } }

Find the first character with count 1 and return it

Output

h

Complexity Analysis

Time: O(n) because we scan the string twice: once to count and once to find the first unique character

Space: O(k) where k is the number of unique characters, because we store counts in a hash map

vs Alternative: Compared to checking each character by scanning the string repeatedly (O(n^2)), using a hash map is much faster and efficient

Edge Cases

Empty string

Returns no unique character message

DSA C++

if (result != '\0') { ... } else { cout << "No unique character" << endl; }

All characters repeating

Returns no unique character message

DSA C++

return '\0'; // Return null char if none found

Single character string

Returns that single character as unique

DSA C++

for (char c : s) { if (freq[c] == 1) { return c; } }

When to Use This Pattern

When asked to find the first unique or non repeating element in a sequence, use a hash map to count frequencies and then scan to find the first unique one.

Common Mistakes

Mistake: Checking frequency while counting without a second pass, which misses order
Fix: Always do a second pass over the original string to preserve order when finding the first unique character

Mistake: Using a data structure that does not preserve order, causing wrong first unique character
Fix: Use the original string order for the second pass, not the hash map keys

Summary

Finds the first character in a string that appears only once using a hash map.

Use when you need to identify the earliest unique element efficiently.

Count all characters first, then scan in order to find the first unique one.

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