Problem Description

Given a string s consisting of lowercase English letters, you need to find and return the first letter that appears twice in the string.

The problem guarantees that at least one letter will appear twice in the string.

To clarify what "first letter to appear twice" means: you should return the letter whose second occurrence comes earliest in the string. For example, if you have the string "abcba", the letter 'b' appears at positions 1 and 3, while 'a' appears at positions 0 and 4. Since 'b''s second occurrence (at position 3) comes before 'a''s second occurrence (at position 4), the answer would be 'b'.

The solution uses a Counter (hash table) to track how many times each character has been seen. As we iterate through the string from left to right, we increment the count for each character. The moment any character's count reaches 2, we immediately return that character as it's the first one to appear twice.

Intuition

To find the first letter that appears twice, we need to keep track of which letters we've already seen as we scan through the string. This naturally leads us to think about using some form of memory or storage to remember the letters we've encountered.

The key insight is that we want to detect the exact moment when we see a letter for the second time. We don't need to wait until we've processed the entire string - as soon as we encounter any letter for the second time, that's our answer.

This suggests a single-pass approach where we:

1. Read characters one by one from left to right
2. Keep a record of how many times we've seen each character
3. Stop immediately when we find a character we've seen before

A hash table or counter is perfect for this because it allows us to quickly check and update the count for each character in constant time O(1). When we see a character, we increment its count. If the count becomes 2, we know this is the first character to appear twice (since we're processing left to right), and we can return it immediately.

The beauty of this approach is its simplicity - we don't need to store positions, we don't need multiple passes, and we don't need to compare different characters' second occurrences. The linear scan guarantees that the first character to reach a count of 2 is indeed the first character to appear twice in the string.

Solution Approach

The solution uses a hash table (Counter in Python) to track the occurrence count of each character as we traverse the string from left to right.

Here's the step-by-step implementation:

1. Initialize a Counter: We create an empty Counter() object (which is essentially a hash table) to store the frequency of each character. Initially, all counts are 0.

2. Iterate through the string: We traverse each character c in the string s one by one from left to right.

3. Update the count: For each character encountered, we increment its count in the hash table: cnt[c] += 1

4. Check for second occurrence: Immediately after incrementing, we check if the count has reached 2: if cnt[c] == 2

5. Return the result: As soon as we find a character with count equal to 2, we return that character. This is guaranteed to be the first character to appear twice because we're processing the string sequentially.

The algorithm works because:

• We process characters in order, so the first character to reach count 2 is the first to appear twice
• The hash table gives us O(1) access to check and update counts
• We exit immediately upon finding the answer, avoiding unnecessary processing

Time Complexity: O(n) where n is the length of the string. In the worst case, we might need to traverse almost the entire string.

Space Complexity: O(1) since we're only dealing with lowercase English letters, the hash table can contain at most 26 entries, which is constant space.

Example Walkthrough

Let's walk through the solution with the string s = "abccbaacz".

We'll use a hash table (Counter) to track how many times we've seen each character as we traverse the string from left to right.

Step-by-step process:

1. Initialize: Start with an empty Counter: cnt = {}

2. Process index 0 - character 'a':

   • Increment count: cnt['a'] = 1
   • Check if count equals 2: No (it's 1)
   • Continue
   • State: cnt = {'a': 1}

3. Process index 1 - character 'b':

   • Increment count: cnt['b'] = 1
   • Check if count equals 2: No (it's 1)
   • Continue
   • State: cnt = {'a': 1, 'b': 1}

4. Process index 2 - character 'c':

   • Increment count: cnt['c'] = 1
   • Check if count equals 2: No (it's 1)
   • Continue
   • State: cnt = {'a': 1, 'b': 1, 'c': 1}

5. Process index 3 - character 'c':

   • Increment count: cnt['c'] = 2
   • Check if count equals 2: Yes!
   • Return 'c' immediately

We found our answer! The character 'c' is the first letter to appear twice in the string (at positions 2 and 3).

Note that even though 'a' also appears twice in the string (at positions 0 and 6), and 'b' appears twice (at positions 1 and 5), we encountered 'c''s second occurrence first while scanning left to right. This makes 'c' the correct answer.

The algorithm efficiently identifies the answer in just 4 iterations without needing to process the remaining characters in the string.

Solution Implementation

Time and Space Complexity

The time complexity is O(n) where n is the length of the string s. This is because we iterate through each character in the string exactly once in the worst case, and each operation inside the loop (incrementing the counter and checking if count equals 2) takes constant time O(1).

The space complexity is O(C) where C is the size of the character set. Since the problem deals with lowercase English letters (based on the context of finding the first repeated character), C = 26. The Counter dictionary will store at most 26 unique characters, regardless of the input string length. Therefore, the space used by the Counter is bounded by the size of the alphabet rather than the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding "First to Appear Twice"

A common mistake is thinking we need to find the character that appears earliest in its first position, rather than the character whose second occurrence comes first.

Incorrect interpretation:

def repeatedCharacter(self, s: str) -> str:
    # WRONG: Finding character with earliest first position
    seen = set()
    repeated = []
    for char in s:
        if char in seen:
            repeated.append(char)
        seen.add(char)
  
    # Then trying to find which repeated char appeared first
    for char in s:
        if char in repeated:
            return char

Correct approach: Return immediately when any character's count reaches 2, as shown in the original solution.

2. Using a Set Instead of Counter

While using a set seems simpler, it requires additional logic and can be error-prone:

Problematic approach:

def repeatedCharacter(self, s: str) -> str:
    seen = set()
    for char in s:
        if char in seen:  # Found second occurrence
            return char
        seen.add(char)

This actually works correctly, but beginners often make mistakes like adding the character to the set before checking, which breaks the logic:

# WRONG: Adding before checking
seen = set()
for char in s:
    seen.add(char)  # Added first!
    if char in seen:  # This is always True!
        return char

3. Over-complicating with Position Tracking

Some might try to track positions explicitly, which is unnecessary:

Overcomplicated:

def repeatedCharacter(self, s: str) -> str:
    positions = {}
    for i, char in enumerate(s):
        if char not in positions:
            positions[char] = []
        positions[char].append(i)
        if len(positions[char]) == 2:
            return char

Solution: Stick to the simple Counter approach or set-based approach. You don't need to track positions since we process characters sequentially.

4. Not Returning Immediately

Continuing to process after finding the answer wastes time:

Inefficient:

def repeatedCharacter(self, s: str) -> str:
    char_count = Counter()
    result = None
    for char in s:
        char_count[char] += 1
        if char_count[char] == 2 and result is None:
            result = char  # Stores but continues iterating
    return result

Solution: Use return char immediately when count reaches 2 to exit the function early.