algoadvance

Leetcode 2351. First Letter to Appear Twice

Problem Statement

LeetCode Problem 2351: First Letter to Appear Twice

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

Example:

  1. Input: s = "abccbaacz" Output: c

  2. Input: s = "abcdd" Output: d

Clarifying Questions

  1. Input Constraints:
    • The input string s will have a length from 1 to 100.
    • The input string s consists of lowercase English letters only.
  2. Output Constraints:
    • The function should return a single character which is the first letter to appear twice.

Strategy

  1. Use a Set for Tracking:
    • We can use a set to keep track of characters that we’ve already seen.
    • We iterate through the string character by character. For each character, we check if it is already in the set:
      • If it is, then it is the first character to appear twice, so we return it.
      • If it is not, we add it to the set and move on to the next character.
    • Since we are iterating through the string only once and checking the set takes constant time, this approach is efficient.

Code

#include <iostream>
#include <unordered_set>
#include <string>

char repeatedCharacter(const std::string& s) {
    std::unordered_set<char> seen;
    for (char ch : s) {
        if (seen.find(ch) != seen.end()) {
            return ch;
        }
        seen.insert(ch);
    }
    return '\0';  // This should never be reached due to problem constraints.
}

int main() {
    std::string s1 = "abccbaacz";
    std::string s2 = "abcdd";
    
    std::cout << "First repeated character in \"" << s1 << "\" is: " << repeatedCharacter(s1) << std::endl;
    std::cout << "First repeated character in \"" << s2 << "\" is: " << repeatedCharacter(s2) << std::endl;
    
    return 0;
}

Time Complexity

This problem is efficiently solved using the above approach and handles all given constraints per the problem statement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI