2351. First Letter to Appear Twice

Problem Description

Given a string s consisting of lowercase English letters, find the first letter that appears twice in the string. The "first" letter is defined as the letter whose second occurrence has the smallest index in the string.

Solution Approaches and Code

Two efficient solutions exist: using a hash table (or array) and using bit manipulation.

Solution 1: Hash Table (or Array)

This approach uses a hash table (or an array of size 26 for lowercase English letters) to store the counts of each character encountered so far. We iterate through the string. For each character:

1. Increment Count: Increment the count of that character in the hash table (or array).
2. Check for Second Occurrence: If the count becomes 2, it's the first repeated character, and we return it.

Time Complexity: O(n), where n is the length of the string. We iterate through the string once. Space Complexity: O(1) (using an array), or O(k) in the worst case if using a hash table where k is the number of unique characters (but it will be at most 26 in this problem).

from collections import Counter
 
class Solution:
    def repeatedCharacter(self, s: str) -> str:
        cnt = Counter()
        for c in s:
            cnt[c] += 1
            if cnt[c] == 2:
                return c
 

class Solution {
    public char repeatedCharacter(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
            if (cnt[c - 'a'] == 2) {
                return c;
            }
        }
        return ' '; //Should not reach here as problem statement guarantees a repeated character
    }
}

class Solution {
public:
    char repeatedCharacter(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
            if (count[c - 'a'] == 2) {
                return c;
            }
        }
        return ' '; //Should not reach here
    }
};

(Other languages like Go, Javascript, TypeScript, Rust etc. would have very similar implementations following the same logic.)

Solution 2: Bit Manipulation

This method is space-efficient, using a single integer mask to track which characters have appeared. Each bit in the integer represents a character (0-25 for a-z).

1. Initialize Mask: Start with mask = 0.
2. Iterate: For each character, calculate its bit position (i = c - 'a').
3. Check Bit: If the i-th bit in mask is already set (meaning the character has appeared before), return the character.
4. Set Bit: Otherwise, set the i-th bit in mask.

Time Complexity: O(n) Space Complexity: O(1) (constant space, regardless of input size)

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        mask = 0
        for c in s:
            i = ord(c) - ord('a')
            if (mask >> i) & 1:
                return c
            mask |= 1 << i

class Solution {
    public char repeatedCharacter(String s) {
        int mask = 0;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if ((mask >> i & 1) == 1) {
                return c;
            }
            mask |= 1 << i;
        }
        return ' '; //Should not reach here
    }
}

(Again, other languages would follow similar principles.)

Both solutions achieve linear time complexity, but the bit manipulation approach is slightly more space-efficient because it uses a constant amount of extra space regardless of the input size. The hash table approach's space complexity is technically O(1) in the context of this problem because the alphabet is fixed, but it could grow larger if the character set were different.