First Letter to Appear Twice - Solution & Explanation

Problem Overview: You receive a lowercase string s. Exactly one character appears twice before any other repeated character. The task is to return the first letter whose second occurrence appears earliest while scanning from left to right.

The constraint that the string only contains lowercase English letters makes the problem straightforward. You only need to detect the first repeated character while iterating through the string once. Efficient solutions rely on constant‑time membership checks using structures like a hash table or a fixed-size counting array.

Approach 1: Using a Set for Tracking Seen Characters (O(n) time, O(1) space)

Scan the string from left to right and maintain a set (or hash set) of characters that have already appeared. For each character, check whether it exists in the set. If it does, that means this is the second occurrence and it must be the earliest repeated character because the string is processed sequentially. Return that character immediately. If it is not in the set, insert it and continue scanning.

The key insight is that a hash lookup runs in constant time. Each character is processed exactly once, making the algorithm linear. Since the alphabet size is fixed (26 lowercase letters), the set never grows beyond 26 elements, so the space usage is effectively constant. This approach is simple, readable, and commonly expected in interviews when solving problems involving repeated elements in a string.

Approach 2: Using an Array for Counting Occurrences (O(n) time, O(1) space)

Instead of a hash-based structure, use a fixed integer array of size 26 to track character frequencies. Convert each character to an index using index = ch - 'a'. While iterating through the string, increment the corresponding counter. The moment a counter becomes 2, you have found the first letter whose second appearance occurs earliest, so return it immediately.

This approach works because the input domain is limited to lowercase English letters. Array indexing is faster and more memory‑predictable than a hash structure. Many low-level implementations in C or Java prefer this technique because it avoids hashing overhead and uses direct indexing, a common pattern in counting-based problems.

Recommended for interviews: The set-based approach is usually the first solution developers write because it directly models the idea of tracking previously seen characters. It demonstrates understanding of hash-based lookup and produces clean code. The counting-array version shows awareness of constraints and optimization opportunities. Interviewers typically accept either solution since both run in O(n) time with O(1) space, but explaining why the fixed-size array works can show stronger problem-solving awareness.