First Letter to Appear Twice

First Letter to Appear Twice

1. What is this problem about?

The First Letter to Appear Twice interview question is a basic frequency-tracking task. You are given a string s, and you need to find the first character that occurs for the second time. The "first" here refers to the order in which the second occurrence is encountered while scanning the string from left to right.

2. Why is this asked in interviews?

Companies like Apple and Google use the First Letter to Appear Twice coding problem as a warm-up. It tests a candidate's ability to use Hash Tables or bitmasks for efficient lookups. It evaluations if you can solve a problem in $O(N)$ time and $O(1)$ or $O( ext{alphabet size})$ space. It’s an essential test of linear scanning and membership checking.

3. Algorithmic pattern used

This problem follows the Hash Set for Membership pattern.

1. Initialize: Create an empty Hash Set (or a boolean array of size 26 for 'a'-'z').
2. Iterate: Traverse the string character by character.
3. Check and Store:
   • If the character is already in the set, it is the first to appear twice. Return it immediately.
   • Otherwise, add the character to the set.
4. Bitmask optimization: Since there are only 26 letters, you can use a single 32-bit integer as a bitmask to track seen characters.

4. Example explanation

String: "abccba"

1. 'a': not in set. Set: {a}.
2. 'b': not in set. Set: {a, b}.
3. 'c': not in set. Set: {a, b, c}.
4. 'c': ALREADY IN SET! Result: 'c'. (Note that 'b' and 'a' also appear twice later, but 'c' is the first to complete its second occurrence).

5. Common mistakes candidates make

• Frequency counting first: Using a two-pass approach to count all frequencies first. This might lead to returning the character that appears most often, rather than the one whose second occurrence comes first.
• Nested loops: Using $O(N^2)$ to check every character against all previous ones.
• Sorting: Sorting the string, which destroys the positional information needed to determine "first occurrence."

6. Interview preparation tip

Always look for the "Early Return" opportunity. In problems where you need the "first" item satisfying a condition, you should return as soon as the condition is met rather than finishing the loop. This shows an optimization-oriented mindset.