#2351

Easy

LeetCode Problem Workspace

First Letter to Appear Twice

Find the first letter that repeats in a string using hash table tracking and early detection for efficiency.

hash table string bit manipulation counting

Problem Statement

Given a string s containing only lowercase English letters, determine the first character that appears twice. The string is guaranteed to have at least one repeated character.

For example, if s = "abccbaacz", the correct output is 'c', because it is the first letter whose second occurrence happens before any other letter repeats. You must return this character efficiently using a hash table approach.

Examples

Example 1

Input: s = "abccbaacz"

Output: "c"

The letter 'a' appears on the indexes 0, 5 and 6. The letter 'b' appears on the indexes 1 and 4. The letter 'c' appears on the indexes 2, 3 and 7. The letter 'z' appears on the index 8. The letter 'c' is the first letter to appear twice, because out of all the letters the index of its second occurrence is the smallest.

Example 2

Input: s = "abcdd"

Output: "d"

The only letter that appears twice is 'd' so we return 'd'.

Constraints

2 <= s.length <= 100
s consists of lowercase English letters.
s has at least one repeated letter.

Solution Approach

Use a Hash Set for Tracking

Iterate through each character in the string and add it to a hash set. If a character is already in the set, immediately return it. This approach directly applies the hash table plus string pattern to detect repeats quickly.

Consider Bit Manipulation for Lowercase Letters

Since the string contains only lowercase letters, you can use a 26-bit integer to track seen characters. Set the corresponding bit for each character and check if the bit is already set. This is an optimized variant of the hash set method with constant space.

Linear Scan with Early Exit

Scan the string from left to right, keeping track of all seen letters in a set. The moment a repeat is found, return it. Early exit prevents unnecessary iterations and matches the problem's main failure mode: missing the first repeated character.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the length of the string, since each character is processed once. Space complexity is O(1) if using a 26-bit mask or O(k) for a hash set with k unique letters.

What Interviewers Usually Probe

Looking for O(n) solution using a hash table or bitmask.
Expect early return as soon as a repeat is detected.
Consider edge cases with multiple repeated letters.

Common Pitfalls or Variants

Common pitfalls

Returning the first seen character instead of the first to repeat.
Failing to handle strings where the repeated character is at the end.
Using nested loops, resulting in O(n^2) time instead of O(n).

Follow-up variants

Return the first character to appear k times instead of twice.
Find the first repeated substring of length 2 or more.
Determine the last character to repeat instead of the first.

FAQ

What is the main strategy to solve First Letter to Appear Twice?

Use a hash set to track seen letters and return the first character that is already in the set during a linear scan.

Can bit manipulation replace a hash set for this problem?

Yes, a 26-bit integer can efficiently track lowercase letters, checking and setting bits as you iterate.

What is the time complexity for detecting the first repeated letter?

It is O(n) because each character is processed exactly once, with immediate return upon repetition.

What should I watch out for when implementing the solution?

Avoid returning the first letter you see or using nested loops, which would ignore the earliest repeat and increase complexity.

How does this problem illustrate the Hash Table plus String pattern?

It demonstrates using a hash table to efficiently track string elements and detect duplicates in a single pass.

terminal

Solution

Solution 1: Array or Hash Table

We traverse the string $s$, using an array or hash table `cnt` to record the occurrence of each letter. When a letter appears twice, we return that letter.

1

2

3

4

5

6

7

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

Solution 2: Bit Manipulation

We can also use an integer `mask` to record whether each letter has appeared, where the $i$-th bit of `mask` indicates whether the $i$-th letter has appeared. When a letter appears twice, we return that letter.

1

2

3

4

5

6

7

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

Continue Practicing

#2506 count pairs of similar strings #1684 count the number of consistent strings #2384 largest palindromic number