We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

First Letter to Appear Twice

Number: 2427

Difficulty: Easy

Paid? No

Companies: Apple, Amazon, Google

Problem Description

Given a string s consisting of lowercase English letters, find and return the first letter that appears twice. A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b. The string is guaranteed to have at least one repeated letter.

Key Insights

  • Use a hash set to track letters that have been seen.
  • Traverse the string and check if the current letter has already been seen.
  • The moment a letter is seen for the second time, return it as the answer.
  • Since the string length is at most 100, a simple linear scan is efficient.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as there is at most 26 lowercase letters stored in the set.

Solution

The solution involves iterating over each character in the input string and checking if it has already been encountered. To do this, we use a hash set:

  1. Initialize an empty set.
  2. Walk through each character in the string.
  3. For each character, check if it exists in the set:
    • If it does, that's the first letter to appear twice, so return it.
    • Otherwise, add the character to the set. This approach ensures that we only traverse the string once, yielding a linear time solution with constant space usage due to the limited alphabet size.

Code Solutions

# Python solution
def first_letter_to_appear_twice(s):
    # Set to store seen letters
    seen_letters = set()
    # Iterate through each character in the string
    for letter in s:
        # Check if the letter has already been seen
        if letter in seen_letters:
            # First letter found to appear twice, return it
            return letter
        # Add the current letter to the set
        seen_letters.add(letter)
    # This line is technically unreachable because input guarantees a repeat
    return None

# Example usage:
# print(first_letter_to_appear_twice("abccbaacz"))
← Back to All Questions