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 <= 100s consists of lowercase English letterss has at least one repeated letter
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show 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
Show PY Solution
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 ""