First Non Repeating Character Using Hash in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of First Non Repeating Character Index

What is the output of the following C++ code that finds the index of the first non-repeating character in the string?

DSA C++

int firstNonRepeatingCharIndex(const std::string& s) {
    std::unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    for (int i = 0; i < s.size(); i++) {
        if (freq[s[i]] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    std::string s = "swiss";
    std::cout << firstNonRepeatingCharIndex(s) << std::endl;
    return 0;
}

A 2

B 4

C 1

D -1

💡 Hint

Check the frequency of each character and find the first with frequency 1.

The string "swiss" has characters: s(3 times), w(1 time), i(1 time). The first non-repeating character is 'w' at index 1.

❓ Predict Output

intermediate

Output when no non-repeating character exists

What is the output of the code when the input string has all repeating characters?

DSA C++

int firstNonRepeatingCharIndex(const std::string& s) {
    std::unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    for (int i = 0; i < s.size(); i++) {
        if (freq[s[i]] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    std::string s = "aabbcc";
    std::cout << firstNonRepeatingCharIndex(s) << std::endl;
    return 0;
}

A -1

B 0

C 1

D 6

💡 Hint

If no character appears once, the function returns -1.

All characters repeat, so no non-repeating character exists. The function returns -1.

🔧 Debug

advanced

Identify the error in this hash-based first non-repeating character code

What error will this code produce when run?

DSA C++

int firstNonRepeatingCharIndex(const std::string& s) {
    std::unordered_map<char, int> 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) {
            return i;
        }
    }
    return -1;
}

A Returns -1 always

B Runtime error: out_of_range

C Compiles but returns wrong index

D No error, works correctly

💡 Hint

Check the loop boundary in the first for loop.

The loop runs from i=0 to i<=s.size(), which accesses s[s.size()] causing out_of_range error.

🧠 Conceptual

advanced

Why use a hash map for first non-repeating character?

Why is a hash map (unordered_map) used to find the first non-repeating character in a string?

A To store frequency of each character for quick lookup

B To store characters in insertion order

C To reverse the string efficiently

D To sort characters alphabetically

💡 Hint

Think about how to count characters quickly.

Hash map stores frequency counts allowing O(1) average lookup to check if a character repeats.

❓ Predict Output

expert

Output of modified code with character removal

What is the output of this code that removes characters from the hash map after counting?

DSA C++

int firstNonRepeatingCharIndex(const std::string& s) {
    std::unordered_map<char, int> freq;
    for (char c : s) {
        if (freq.find(c) == freq.end()) {
            freq[c] = 1;
        } else {
            freq.erase(c);
        }
    }
    for (int i = 0; i < s.size(); i++) {
        if (freq.find(s[i]) != freq.end()) {
            return i;
        }
    }
    return -1;
}

int main() {
    std::string s = "aabbcdde";
    std::cout << firstNonRepeatingCharIndex(s) << std::endl;
    return 0;
}

A -1

B 6

C 0

D 4

💡 Hint

Characters repeated are erased, so only unique remain in map.

Characters 'a','b','d' repeat and are erased. Remaining unique are 'c' at index 4 and 'e' at index 7. The first unique is 'c' at index 4.

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