To solve this problem, iterate through the string from left to right and maintain a hash set of seen letters. As soon as a letter appears that already exists in the set, return it immediately. This method ensures the first repeated letter is found efficiently with linear time and minimal space overhead.
Problem Statement
Given a string s containing only lowercase English letters, determine the first character that appears twice. The string is guaranteed to have at least one repeated character.
For example, if s = "abccbaacz", the correct output is 'c', because it is the first letter whose second occurrence happens before any other letter repeats. You must return this character efficiently using a hash table approach.
Examples
Example 1
Input: s = "abccbaacz"
Output: "c"
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"
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.
Solution Approach
Use a Hash Set for Tracking
Iterate through each character in the string and add it to a hash set. If a character is already in the set, immediately return it. This approach directly applies the hash table plus string pattern to detect repeats quickly.
Consider Bit Manipulation for Lowercase Letters
Since the string contains only lowercase letters, you can use a 26-bit integer to track seen characters. Set the corresponding bit for each character and check if the bit is already set. This is an optimized variant of the hash set method with constant space.
Linear Scan with Early Exit
Scan the string from left to right, keeping track of all seen letters in a set. The moment a repeat is found, return it. Early exit prevents unnecessary iterations and matches the problem's main failure mode: missing the first repeated character.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) where n is the length of the string, since each character is processed once. Space complexity is O(1) if using a 26-bit mask or O(k) for a hash set with k unique letters.
What Interviewers Usually Probe
- Looking for O(n) solution using a hash table or bitmask.
- Expect early return as soon as a repeat is detected.
- Consider edge cases with multiple repeated letters.
Common Pitfalls or Variants
Common pitfalls
- Returning the first seen character instead of the first to repeat.
- Failing to handle strings where the repeated character is at the end.
- Using nested loops, resulting in O(n^2) time instead of O(n).
Follow-up variants
- Return the first character to appear k times instead of twice.
- Find the first repeated substring of length 2 or more.
- Determine the last character to repeat instead of the first.
How GhostInterview Helps
- Highlights early detection patterns for repeated characters.
- Provides direct hash table and bit manipulation implementations.
- Visualizes why a character's second occurrence is the decisive factor.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy to solve First Letter to Appear Twice?
Use a hash set to track seen letters and return the first character that is already in the set during a linear scan.
Can bit manipulation replace a hash set for this problem?
Yes, a 26-bit integer can efficiently track lowercase letters, checking and setting bits as you iterate.
What is the time complexity for detecting the first repeated letter?
It is O(n) because each character is processed exactly once, with immediate return upon repetition.
What should I watch out for when implementing the solution?
Avoid returning the first letter you see or using nested loops, which would ignore the earliest repeat and increase complexity.
How does this problem illustrate the Hash Table plus String pattern?
It demonstrates using a hash table to efficiently track string elements and detect duplicates in a single pass.
Need direct help with First Letter to Appear Twice instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture First Letter to Appear Twice from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Count similar string pairs by converting each word into a character-set signature and counting matching signatures efficiently.
Open problem page#1684 Count the Number of Consistent StringsCount the number of strings fully composed of allowed characters using array scanning and hash lookup for efficiency.
Open problem page#2384 Largest Palindromic NumberForm the largest palindromic number from a string of digits while maintaining a valid palindrome structure.
Open problem page