Scale Engineer

First Letter to Appear Twice

Easy
#2141Time: 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.
Patterns
Bit ManipulationCounting
Data structures
Hash TableString

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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.
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 ' ';    }}

Complexity

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.

Trade-offs

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.

Solutions

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;      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem