Problem Statement
Given a string s consisting of lowercase English letters, return the first letter to appear twice.
Notes
- A letter
a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
- The string will contain at least one letter that appears twice.
Example
-
Input: s = "abccbaacz"
Output: "c"
Explanation:
- The letter
'c' is the first to appear twice because the index of its second occurrence is the smallest.
-
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.
Brute Force Approach
Approach
Idea: Compare each character of the string with every subsequent character to find the first letter that appears twice.
Steps
- Loop through each character in the string.
- For each character, loop through the remaining part of the string to check if it appears again.
- Return the first character that appears twice.
Time & Space Complexity
- Time Complexity: O(n²)
- For each character, we iterate through the remaining part of the string.
- Space Complexity: O(1)
- No additional data structures are used.
Code Snippet
Dry Run
Input: s = "abccbaacz"
- Compare
'a' at index 0 with subsequent characters. No match found.
- Compare
'b' at index 1 with subsequent characters. No match found.
- Compare
'c' at index 2 with 'c' at index 3. Match found.
- Return
'c'.
Efficient Approach Using a Queue
Approach
Idea: Use a queue to store characters as they are encountered. Simultaneously, use a hash set to track characters that have already been seen. The first character added to the queue that has already been seen is the answer.
Steps
- Initialize a queue to process characters and a hash set to track seen characters.
- Loop through the string:
- If the character is in the hash set, return it as the first repeated character.
- Otherwise, add it to the hash set and the queue.
- If no repeated character is found (shouldn't happen due to constraints), return
null.
Time & Space Complexity
- Time Complexity: O(n)
- Each character is processed once.
- Space Complexity: O(n)
- The queue and hash set store up to
n elements.
Code Snippet
Dry Run
Input: s = "abccbaacz"
- Process
'a'. Add to queue and hash set:
- Queue:
['a'], Seen: { 'a' }.
- Process
'b'. Add to queue and hash set:
- Queue:
['a', 'b'], Seen: { 'a', 'b' }.
- Process
'c'. Add to queue and hash set:
- Queue:
['a', 'b', 'c'], Seen: { 'a', 'b', 'c' }.
- Process
'c'. Found in hash set.
Complexity Analysis
| Operation | Brute Force | Optimized Using Queue |
|---|
| Time Complexity | O(n²) | O(n) |
| Space Complexity | O(1) | O(n) |
Conclusion
- The brute force approach is simple but has two major drawbacks:
- It is inefficient due to its O(n²) time complexity from comparing all pairs of characters.
- More importantly, it may not correctly identify the first occurrence of a repeated letter. When comparing all pairs, we could find a later repeated letter before finding the actual first repeated letter in the string. For example, in "abba", comparing all pairs could find the second 'b' before finding the second 'a', even though 'a' repeats first.
- Using a queue with a hash set optimizes the solution to O(n) time complexity while maintaining readability and structure.
- This approach demonstrates the practical use of a queue for character processing.