First Letter to Appear Twice — Problem & Solution
First Letter to Appear Twice solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
First Letter to Appear Twice is an easy coding problem on strings and hash table, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s of lowercase English letters, return the first letter whose second occurrence comes earliest.
The input is guaranteed to contain at least one repeated letter.
Example 1
Input: s = "abccbaacz"
Output: c
Explanation: c is the first letter to appear a second time, at index 3.
Example 2
Input: s = "abcdd"
Output: d
Example 3
Input: s = "aa"
Output: a
Constraints
2 <= s.length <= 100s consists of lowercase English letters.At least one letter appears more than once.
Hints for First Letter to Appear Twice
Hint 1
Scan left to right and remember which letters you have already seen.
Hint 2
The moment a letter is seen for the second time, that is the answer.
Hint 3
A 26-slot boolean array is enough state.
How to solve First Letter to Appear Twice
"The letter whose second occurrence is earliest" is exactly the first letter that is already in the seen-set when you reach it.
Approach
- Keep a set (or 26-slot boolean array) of letters seen so far.
- Walk the string. If the current letter is already in the set, return it.
- Otherwise add it and continue.
Why it works
The scan reaches each index in order, so the first time the set test succeeds is the earliest second occurrence in the whole string.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Counting frequencies first and then picking the letter with the smallest first index gives the wrong letter — the tie-break is on the second occurrence.
- A bitmask over 26 bits is a compact alternative to the boolean array.
Reference solution
Python
def repeatedCharacter(s: str) -> str:
seen = set()
for c in s:
if c in seen:
return c
seen.add(c)
return ""Java
public static String repeatedCharacter(String s) {
boolean[] seen = new boolean[26];
for (int i = 0; i < s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (seen[idx]) return String.valueOf(s.charAt(i));
seen[idx] = true;
}
return "";
}C++
string repeatedCharacter(string s) {
bool seen[26] = { false };
for (char c : s) {
if (seen[c - 'a']) return string(1, c);
seen[c - 'a'] = true;
}
return "";
}JavaScript
var repeatedCharacter = function(s) {
const seen = {};
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
if (seen[c] === true) return c;
seen[c] = true;
}
return "";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets