# First Letter to Appear Twice
**Difficulty:** EASY
[External](https://leetcode.com/problems/first-letter-to-appear-twice)
Canonical: https://scaleengineer.com/dsa/problems/first-letter-to-appear-twice
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## 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.

# Approaches
## Brute Force with Nested Loops
This straightforward approach involves checking every character against all preceding characters to find the first duplicate. It uses two nested loops, making it simple to conceptualize but less efficient for larger inputs.
**Time:** O(N^2), where N is the length of the string. The nested loops lead to a quadratic number of comparisons in the worst-case scenario (e.g., `"ab...yzzy...ba"`). · **Space:** O(1), as no extra data structures are used that scale with the input size. Only a few variables for loop indices are needed.
**Pros:** Very simple to understand and implement.; Requires no additional space.
**Cons:** Inefficient due to its O(N^2) time complexity, making it slow for large strings.
### Explanation
The algorithm iterates through the string starting from the second character (index 1). For each character, it scans all the characters that came before it. If a match is found, it means the current character is a duplicate. Because we process the string from left to right, the first such duplicate we find is guaranteed to be the one with the earliest second occurrence.

For example, in `s = "abccbaacz"`:
- When the outer loop is at index 3 (`c`), the inner loop checks indices 0, 1, 2.
- At index 2, it finds a match (`s[2] == s[3]`).
- The character `c` is returned immediately.

```java
class Solution {
    public char repeatedCharacter(String s) {
        int n = s.length();
        for (int i = 1; i < n; i++) {
            char currentChar = s.charAt(i);
            for (int j = 0; j < i; j++) {
                if (s.charAt(j) == currentChar) {
                    return currentChar;
                }
            }
        }
        // This part is unreachable given the problem constraints.
        return ' ';
    }
}
```
### Algorithm
- Iterate through the string with an index `i` from 1 to `n-1` (where `n` is the string length).
- For each `i`, start an inner loop with an index `j` from 0 to `i-1`.
- Compare the character at index `i` with the character at index `j`.
- If `s.charAt(i) == s.charAt(j)`, a character has appeared for the second time. Return `s.charAt(i)`.

## Single Pass using a Set
A more optimal approach is to use a hash set to keep track of characters we've already seen. By iterating through the string just once, we can efficiently find the first character that appears for a second time.
**Time:** O(N), where N is the length of the string. We traverse the string only once. · **Space:** O(k), where `k` is the number of unique characters. Since the input is limited to 26 lowercase English letters, the space complexity is constant, i.e., O(1).
**Pros:** Optimal time complexity of O(N).; The logic is clean and easy to follow.
**Cons:** Uses extra space for the hash set or boolean array, although it's a constant amount.
### Explanation
We can solve this problem in a single pass. We'll use a data structure, like a `HashSet`, to store the characters we have encountered so far. As we iterate through the string from left to right:

1. For each character, we first check if it's already in our `HashSet`.
2. If it is, we've found our answer. This is the second time we're seeing this character, and since we're iterating from the start of the string, this must be the first letter to appear twice according to the problem's definition.
3. If the character is not in the set, we add it and move to the next character.

This method is efficient because hash set lookups and insertions take constant time on average.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public char repeatedCharacter(String s) {
        Set<Character> seen = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen.contains(c)) {
                return c;
            }
            seen.add(c);
        }
        // This part is unreachable given the problem constraints.
        return ' ';
    }
}
```

Since the input consists only of lowercase English letters, a boolean array of size 26 could also be used instead of a `HashSet` for slightly better performance, as it avoids hashing overhead.

```java
class Solution {
    public char repeatedCharacter(String s) {
        boolean[] seen = new boolean[26];
        for (char c : s.toCharArray()) {
            if (seen[c - 'a']) {
                return c;
            }
            seen[c - 'a'] = true;
        }
        // This part is unreachable given the problem constraints.
        return ' ';
    }
}
```
### Algorithm
- Initialize an empty `HashSet` named `seen`.
- Iterate through each character `c` of the input string `s`.
- For each `c`, check if `seen` already contains `c`.
- If it does, `c` is the first letter to appear twice. Return `c`.
- If not, add `c` to the `seen` set and continue.

# Solutions
### Java

```java
class Solution {
public
  char repeatedCharacter(String s) {
    int[] cnt = new int[26];
    for (int i = 0;; ++i) {
      char c = s.charAt(i);
      if (++cnt[c - 'a'] == 2) {
        return c;
      }
    }
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def repeatedCharacter(self, s: str) -> str: cnt = Counter() for c in s: cnt[c] += 1 if cnt[c] == 2: return c

```