First Letter to Appear Twice

Description

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

Note: A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b. The string s will contain at least one letter that appears twice.

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 to appear twice because its second occurrence at index 3 comes before the second occurrence of 'a' at index 5 and 'b' at index 4.

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

Example 3:
Input: s = "aa"
Output: "a"
Explanation: The letter 'a' appears twice at indices 0 and 1, making it the first letter to appear twice.

Constraints

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

Signature

def solution(s: str) -> str: ...

Complexity

Time: O(n)
Space: O(1)

Hints

Pattern: Hash set for tracking seen characters
Approach: Iterate through string, check if char is in set. If yes, return it. Otherwise add to set.
Complexity: O(1) space since at most 26 lowercase letters

Solutions

Python

def solution(s):
    maps = {}

    for i in range(len(s)):
        if s[i] in maps:
            maps[s[i]] += 1
        else:
            maps[s[i]] = 1

        if maps[s[i]] == 2:
            return s[i]

    return ""