Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Examples

Example 1:

Input: s = "leetcode"
Output: 0
Explanation: The character 'l' at index 0 is the first character that does not repeat.

Example 2:

Input: s = "loveleetcode"
Output: 2
Explanation: The character 'v' at index 2 is the first character that does not repeat.

Example 3:

Input: s = "aabb"
Output: -1
Explanation: All characters repeat, so return -1.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of only lowercase English letters.

Thinking Process

  1. Bit Manipulation: Efficient way to track seen-once vs seen-multiple using XOR and AND operations
  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.
Bit manipulation 1 0 1 1 0 1 0 XOR pairs · masks · shifts

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Solution

class Solution {
public:
    int firstUniqChar(string s) {
        int once = 0, multi = 0;
        int idx = -1;
        for(char ch : s) {
            int bit = 1 << (ch - 'a');
            multi |= once & bit;
            once ^= bit;
            once &= ~multi;
        }

        for(int i = 0; i < (int)s.length(); i++) {
            int bit = 1 << (s[i] - 'a');
            if(once & bit) {
                return i;
            }
        }
        return -1;
    }
};

Solution Explanation

Approach: Two pointers on string (this problem)

Key idea: 1. Bit Manipulation: Efficient way to track seen-once vs seen-multiple using XOR and AND operations

How the code works:

  1. Bit Manipulation: Efficient way to track seen-once vs seen-multiple using XOR and AND operations
    • Strings often need frequency maps or two-pointer scans.
    • Watch index bounds and empty-string edge cases.
    • Stack helps with nested or repeated patterns.

Walkthrough — input s = "leetcode", expected output 0:

The character ‘l’ at index 0 is the first character that does not repeat.

Common Mistakes

  1. All unique: s = "abc" → return 0
  2. All duplicate: s = "aabb" → return -1
  3. Single character: s = "a" → return 0
  4. Unique at end: s = "aabbc" → return 4
  5. Unique in middle: s = "aabcc" → return 2 (‘b’)

  6. Long string: All characters unique, return 0

  7. Wrong bit operations: Incorrect XOR/AND logic in bit manipulation
  8. Index confusion: Not tracking first occurrence correctly
  9. Off-by-one: Incorrect character to index conversion
  10. Not handling all duplicates: Forgetting to return -1
  11. Wrong order: Returning last unique instead of first

Key Takeaways

  1. Bit Manipulation: Efficient way to track seen-once vs seen-multiple using XOR and AND operations
  2. Index Tracking: Store first occurrence index to find minimum later
  3. Two-Pass Approach: Count first, then find first unique
  4. Early Exit: Can optimize by scanning string in second pass instead of all 26 characters

References

Template Reference