2351. First Letter to Appear Twice - Solution

Q: 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.

Q: 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 or a 26-length integer array for counting occurrences. Both implementations achieve O(n) time and O(1) space complexity.

The problem

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.

Python

def first_letter_to_appear_twice(s):
    seen = set()
    for char in s:
        if char in seen:
            return char
        seen.add(char)
    return ''

JavaScript

function firstLetterToAppearTwice(s) {
    const seen = new Set();
    for (let char of s) {
        if (seen.has(char)) {
            return char;
        }
        seen.add(char);
    }
    return '';
}

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.

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.

Java

public char firstLetterToAppearTwice(String s) {
    int[] counts = new int[26];
    for (char c : s.toCharArray()) {
        if (++counts[c - 'a'] == 2) {
            return c;
        }
    }
    return ' ';
}

#include <stdio.h>

char firstLetterToAppearTwice(const char* s) {
    int counts[26] = {0};
    for (int i = 0; s[i]; ++i) {
        int index = s[i] - 'a';
        if (++counts[index] == 2) {
            return s[i];
        }
    }
    return '\0';
}

The solution creates a count array for storing occurrences of each letter. By iterating through the string and updating the count for each character, we identify and return the first character with a count of 2.

Complexity

Time Complexity: O(n) with n as the string size.
Space Complexity: O(1) due to fixed-size array.

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.

C++

class Solution {
public:
    char repeatedCharacter(string s) {
        int cnt[26]{};
        for (int i = 0;; ++i) {
            if (++cnt[s[i] - 'a'] == 2) {
                return s[i];
            }
        }
    }
};

TypeScript

function repeatedCharacter(s: string): string {
    const vis = new Array(26).fill(false);
    for (const c of s) {
        const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
        if (vis[i]) {
            return c;
        }
        vis[i] = true;
    }
    return ' ';
}

func repeatedCharacter(s string) byte {
	cnt := [26]int{}
	for i := 0; ; i++ {
		cnt[s[i]-'a']++
		if cnt[s[i]-'a'] == 2 {
			return s[i]
		}
	}
}

Rust

impl Solution {
    pub fn repeated_character(s: String) -> char {
        let mut vis = [false; 26];
        for &c in s.as_bytes() {
            if vis[(c - b'a') as usize] {
                return c as char;
            }
            vis[(c - b'a') as usize] = true;
        }
        ' '
    }
}

PHP

class Solution {
    /**
     * @param String $s
     * @return String
     */
    function repeatedCharacter($s) {
        for ($i = 0; ; $i++) {
            $hashtable[$s[$i]] += 1;
            if ($hashtable[$s[$i]] == 2) {
                return $s[$i];
            }
        }
    }
}

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.

C++

class Solution {
public:
    char repeatedCharacter(string s) {
        int mask = 0;
        for (int i = 0;; ++i) {
            if (mask >> (s[i] - 'a') & 1) {
                return s[i];
            }
            mask |= 1 << (s[i] - 'a');
        }
    }
};

TypeScript

function repeatedCharacter(s: string): string {
    let mask = 0;
    for (const c of s) {
        const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
        if (mask & (1 << i)) {
            return c;
        }
        mask |= 1 << i;
    }
    return ' ';
}

func repeatedCharacter(s string) byte {
	mask := 0
	for i := 0; ; i++ {
		if mask>>(s[i]-'a')&1 == 1 {
			return s[i]
		}
		mask |= 1 << (s[i] - 'a')
	}
}

Rust

impl Solution {
    pub fn repeated_character(s: String) -> char {
        let mut mask = 0;
        for &c in s.as_bytes() {
            if (mask & (1 << ((c - b'a') as i32))) != 0 {
                return c as char;
            }
            mask |= 1 << ((c - b'a') as i32);
        }
        ' '
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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) with n as the string size. Space Complexity: O(1) due to fixed-size array.
Array or Hash Table	–
Bit Manipulation	–

Complexity analysis

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

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.

First Letter to Appear Twice solution and explanation

The problem

Approach overview

Approach 1: Using a Set for Tracking Seen Characters

Approach 2: Using an Array for Counting Occurrences

Approach 3: Array or Hash Table

Approach 4: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

First Letter to Appear Twice solution and explanation

The problem

Approach overview

Approach 1: Using a Set for Tracking Seen Characters

Approach 2: Using an Array for Counting Occurrences

Approach 3: Array or Hash Table

Approach 4: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems