Lesson

10.7First Letter to Appear Twice

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 <= 100
s 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.
- Return 'c'.

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:
1. It is inefficient due to its O(n²) time complexity from comparing all pairs of characters.
2. 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.

Previous Next