algoadvance

You are given a string s consisting of lowercase English letters. Determine the first character that repeats in the string and return it. If no character repeats, return an empty string.

Clarifying Questions

1. Q: Can we assume the input string only contains lowercase English letters? A: Yes.

2. Q: Is it possible for the input string to be empty? A: Yes, and if the string is empty, the function should return an empty string.

3. Q: Should we consider non-consecutive repeats? A: Yes, any character that appears more than once in the string.

4. Q: What should be returned if there are no repeated characters in the string? A: An empty string.

Strategy

1. Iterate through the string while keeping track of characters that we have already seen.
2. Use a set to store characters as they appear.
3. For each character:
   • If the character has already been seen, return that character as it is the first one to appear twice.
   • If the character has not been seen, add it to the set for tracking.
4. If no character repeats, return an empty string.

Code

def first_letter_to_appear_twice(s: str) -> str:
    seen = set()
    
    for char in s:
        if char in seen:
            return char
        seen.add(char)
    
    return ""

Time Complexity

• Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once.
• Space Complexity: O(min(n, 26)), because we are storing each unique character in a set, and there are at most 26 unique lowercase English letters.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?