First Letter to Appear Twice

Easy
536.

First Letter to Appear Twice

First Letter to Appear Twice is an easy coding problem on strings and hash table, asked in Amazon and Infosys interviews.

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 <= 100
  • s consists of lowercase English letters.
  • At least one letter appears more than once.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var repeatedCharacter = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • s consists of lowercase English letters.
  • At least one letter appears more than once.

Hints for First Letter to Appear Twice

  1. Hint 1

    Scan left to right and remember which letters you have already seen.

  2. Hint 2

    The moment a letter is seen for the second time, that is the answer.

  3. 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

  1. Keep a set (or 26-slot boolean array) of letters seen so far.
  2. Walk the string. If the current letter is already in the set, return it.
  3. 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