Given a string s consisting of lowercase English letters, return the first letter to appear twice.
Note:
a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.s will contain at least one letter that appears twice.
Example 1:
Input: s = "abccbaacz" Output: "c" Explanation: 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" Explanation: The only letter that appears twice is 'd' so we return 'd'.
Constraints:
2 <= s.length <= 100s consists of lowercase English letters.s has at least one repeated letter.This approach involves iterating through the string and using a set data structure to keep track of characters that have already been seen. As soon as a character that has been seen before is found, we return it.
The function initializes an empty set called seen. As we iterate through the string s, we check if the character is already in the set. If it is, we return that character as it is the first to appear twice. Otherwise, we add the character to the set.
JavaScript
Time Complexity: O(n) because each operation of adding to or checking membership of a set is O(1).
Space Complexity: O(1) as the space used by the set is limited to a constant size (26 letters)
This approach counts occurrences of each character using a fixed-size array where the index corresponds to the character's position in the alphabet. Once a character count exceeds 1, it is returned.
An array of 26 integers representing each lowercase letter is initialized to zero. As we iterate through the string, we increase the count corresponding to the character's index in this array. When a count reaches 2, we return the character.
Java
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since the array size is constant at 26.
| Approach | Complexity |
|---|---|
| Using a Set for Tracking Seen Characters | Time Complexity: O(n) because each operation of adding to or checking membership of a set is O(1). |
| Using an Array for Counting Occurrences | Time Complexity: O(n), where n is the length of the string. |
Leetcode 2351 First Letter to Appear Twice | Easy Peasy Maps • Coding Decoded • 1,353 views views
Watch 9 more video solutions →Practice First Letter to Appear Twice with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor