JuniorCodeCommonNot answered yet
Index of the first non-repeating character
Given a string, return the index of the first character that appears exactly once. If there is no such character, return -1.
Requirements:
"count each character by rescanning" approach.
- Two passes over the string with a frequency table is fine; avoid an O(n²)
int firstUniqueChar(const std::string& s) {
// your code here
}Write the implementation.
First pass: count the occurrences of each character in a hash table (or fixed array for a known alphabet). Second pass: walk the string left to right and return the index of the first character whose count is 1. Return -1 if none. O(n) time.
- ✗Rescanning the string per character, degrading to O(n²)
- ✗Returning the first count-1 entry from an unordered map, losing original order
- ✗Confusing 'first not seen yet' with 'occurs exactly once'
- →Why must the second pass go over the string, not over the map?
- →How would you do it in one pass if you also stored each character's index?
Contents
Task
Return the index of the first character occurring exactly once; otherwise -1. In O(n).
Solution
int firstUniqueChar(const std::string& s) {
std::unordered_map<char, int> count;
for (char c : s) ++count[c]; // first pass: frequencies
for (int i = 0; i < static_cast<int>(s.size()); ++i)
if (count[s[i]] == 1) return i; // second pass: over the string
return -1;
}Key points
- The second pass goes over the string, not the table, to preserve original order.
- "First with count 1" is not the same as "first not yet seen".
- Two passes give O(n); rescanning per character would be O(n²).
Contents
