What is the time complexity of the Hash Set approach?

The Hash Set approach has a time complexity of O(n) where n is the length of the string, as we iterate through the string once and each set operation is O(1) on average.

What is the space complexity of the Bit Manipulation approach?

The Bit Manipulation approach has a space complexity of O(1) as it uses only a single 32-bit integer to track seen characters.

Why is the Brute Force approach less efficient?

The Brute Force approach has a time complexity of O(n²) because for each character, we potentially scan the entire remaining string to find a duplicate.

What is the most space-efficient solution?

The Bit Manipulation approach is the most space-efficient, using only a single integer (32 bits) to track all 26 lowercase letters.

First Letter to Appear Twice

Difficulty: Easy | Acceptance: 75.00% | Paid: No Topics: Hash Table, String, Bit Manipulation, Counting

Given a string s consisting of lowercase English letters, return the first letter to appear twice.

A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b. s contains at least one letter that appears twice.

Examples
Constraints
Hash Set Approach
Boolean Array Approach
Bit Manipulation Approach
Brute Force Approach

Examples

Example 1:

Input: s = "abccbaacz"
Output: "c"
Explanation:
The letter 'a' appears at indices 0, 5 and 6.
The letter 'b' appears at indices 1 and 4.
The letter 'c' appears at indices 2, 3 and 7.
The letter 'z' appears at index 8.
The letter 'c' is the first letter to appear twice, because the second 'c' appears at index 3 which is before the second 'a' at index 5 and the second 'b' at index 4.

Example 2:

Input: s = "abcdd"
Output: "d"
Explanation:
The only letter that appears twice is 'd' so we return 'd'.

Constraints

2 <= s.length <= 100
s consists of lowercase English letters.
s contains at least one letter that appears twice.

Hash Set Approach

Intuition Use a hash set to track characters we’ve seen while iterating through the string. The first character already in the set is our answer.

Steps

Create an empty hash set
Iterate through each character in the string
If the character is already in the set, return it
Otherwise, add the character to the set

python

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        seen = set()
        for ch in s:
            if ch in seen:
                return ch
            seen.add(ch)
        return ""

Complexity

Time: O(n) where n is the length of the string
Space: O(1) since we store at most 26 lowercase letters
Notes: Clean and readable solution with constant space due to limited character set

Boolean Array Approach

Intuition Since we only have lowercase English letters, we can use a fixed-size boolean array of 26 elements to track seen characters, which is more memory-efficient than a hash set.

Steps

Create a boolean array of size 26 initialized to false
Iterate through each character in the string
Calculate the index using character’s ASCII value (ch - ‘a’)
If the value at that index is true, return the character
Otherwise, set the value at that index to true

python

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        seen = [False] * 26
        for ch in s:
            idx = ord(ch) - ord('a')
            if seen[idx]:
                return ch
            seen[idx] = True
        return ""

Complexity

Time: O(n) where n is the length of the string
Space: O(1) with a fixed array of 26 booleans
Notes: More memory-efficient than hash set with direct index access

Bit Manipulation Approach

Intuition Use a single 32-bit integer as a bitset where each bit represents whether a character has been seen. This is the most space-efficient approach.

Steps

Initialize an integer bitmask to 0
Iterate through each character in the string
Calculate the bit position using character’s ASCII value
Check if the bit at that position is already set
If set, return the character
Otherwise, set the bit at that position

python

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        seen = 0
        for ch in s:
            bit = 1 &lt;&lt; (ord(ch) - ord('a'))
            if seen & bit:
                return ch
            seen |= bit
        return ""

Complexity

Time: O(n) where n is the length of the string
Space: O(1) using only a single integer
Notes: Most space-efficient solution with bitwise operations

Brute Force Approach

Intuition For each character, check if it appears again later in the string. The first character with a duplicate is our answer.

Steps

Iterate through each character in the string
For each character, check if it appears in the remaining substring
If found, return that character
Continue until we find the first duplicate

python

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                if s[i] == s[j]:
                    return s[i]
        return ""

Complexity

Time: O(n²) where n is the length of the string
Space: O(1) no additional data structures used
Notes: Simple but inefficient for larger inputs, useful for understanding the problem