Skip to main content
Talentd

First Letter to Appear Twice - Solution & Explanation

EasyHash TableStringBit ManipulationCounting13 min readAsked at: Apple, Google
Practice this problem

Problem Statement

Given a string s consisting of lowercase English letters, return the first letter to appear twice.

Note:

  • A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
  • s will contain at least one letter that appears twice.

 

Example 1:

Input: s = "abccbaacz"
Output: "c"
Explanation:
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"
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.

Approach Overview

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.

Approach 1: Using a Set for Tracking Seen Characters

This approach involves iterating through the string and using a set data structure to keep track of characters that have already been seen. As soon as a character that has been seen before is found, we return it.

The function initializes an empty set called seen. As we iterate through the string s, we check if the character is already in the set. If it is, we return that character as it is the first to appear twice. Otherwise, we add the character to the set.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n) because each operation of adding to or checking membership of a set is O(1).
Space Complexity: O(1) as the space used by the set is limited to a constant size (26 letters)

Try this approach in the editor →

Approach 2: Using an Array for Counting Occurrences

This approach counts occurrences of each character using a fixed-size array where the index corresponds to the character's position in the alphabet. Once a character count exceeds 1, it is returned.

An array of 26 integers representing each lowercase letter is initialized to zero. As we iterate through the string, we increase the count corresponding to the character's index in this array. When a count reaches 2, we return the character.

Code

CJava

C

Java

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since the array size is constant at 26.

Try this approach in the editor →

Approach 3: Array or Hash Table

We traverse the string s, using an array or hash table cnt to record the occurrence of each letter. When a letter appears twice, we return that letter.

The time complexity is O(n) and the space complexity is O(C). Here, n is the length of the string s, and C is the size of the character set. In this problem, C = 26.

Code

PythonJavaC++GoTypeScriptRustPHPC

Python

Java

C++

Go

TypeScript

Rust

PHP

C

Try this approach in the editor →

Approach 4: Bit Manipulation

We can also use an integer mask to record whether each letter has appeared, where the i-th bit of mask indicates whether the i-th letter has appeared. When a letter appears twice, we return that letter.

The time complexity is O(n) and the space complexity is O(1). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a Set for Tracking Seen Characters

Time Complexity: O(n) because each operation of adding to or checking membership of a set is O(1).
Space Complexity: O(1) as the space used by the set is limited to a constant size (26 letters)

Using an Array for Counting Occurrences

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since the array size is constant at 26.

Array or Hash Table—
Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set for tracking seen charactersO(n)O(1)General solution in Python/JavaScript; clean and easy to reason about with constant-time hash lookups
Array for counting occurrencesO(n)O(1)Best when characters are limited to lowercase letters; avoids hashing and uses direct indexing

Video Solution

LeetCode 2351: First Letter to Appear Twice Solution • Engineering Digest • 2,526 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is First Letter to Appear Twice easy or hard?
First Letter to Appear Twice is classified as an Easy problem. It tests basic understanding of hash sets, arrays, and string traversal. The optimal solution requires a single pass through the string with constant-time lookups.
First Letter to Appear Twice Python/Java solution
Python solutions usually use a set to track seen characters during iteration. Java implementations often use either a HashSet<Character> or a 26-length integer array for counting occurrences. Both implementations achieve O(n) time and O(1) space complexity.
How to solve First Letter to Appear Twice in O(n)?
Iterate through the string while storing characters in a hash set. For every character, check if it already exists in the set. If it does, return it immediately because this is the earliest second occurrence. Otherwise insert it into the set and continue scanning.
What is the best approach for First Letter to Appear Twice?
The most common approach is scanning the string once while storing previously seen characters in a hash set. If the current character already exists in the set, it is the first letter whose second occurrence appears earliest. This runs in O(n) time with O(1) space because the set size is limited to 26 lowercase letters.
Is First Letter to Appear Twice asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving hash tables and duplicate detection in strings. Variations of this pattern appear in interviews at companies like Amazon and Google where candidates must detect repeated elements efficiently using O(n) time solutions.
What data structure is used in First Letter to Appear Twice?
Typical solutions use a hash set to track characters that have already appeared. Another common structure is a fixed-size array of length 26 that stores frequency counts for lowercase letters. Both allow constant-time lookups while scanning the string.
What is the time complexity of First Letter to Appear Twice?
The optimal solutions run in O(n) time where n is the length of the string. Each character is processed once with constant-time lookup using either a hash set or a fixed-size counting array. Space complexity is O(1) due to the limited alphabet size.

Ready to solve this problem?

Practice First Letter to Appear Twice with our built-in code editor and test cases.

Practice on FleetCode
Previous

First Unique Character in a String

Next

Two Sum