Jobs

Interviews

Discussions

First Letter to Appear Twice

Easy

Asked by:

55 views

Topics:

Strings

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.

Try coding it in LeetCode

First Letter to Appear Twice

Easy

Asked by:

55 views

Topics:

Strings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of characters that the input string can contain? Is it limited to lowercase English letters, or can it include uppercase letters, numbers, or special characters?
If no character appears twice in the string, what should the function return? Should I return a specific character like null or an empty string, or throw an exception?
Is the input string guaranteed to be non-empty? What should I do if the input string is null or empty?
If there are multiple characters that appear twice, should I return the first one that appears twice in the string (as opposed to the first one to be repeated)?
Are there any constraints on the length of the input string?

Brute Force Solution

Approach

The goal is to find the first letter that repeats in a given set of letters. The brute force strategy is to simply check each letter against all the letters that come after it to see if there's a match.

Here's how the algorithm would work step-by-step:

Take the first letter.
Compare it to every letter that comes after it in the set.
If you find a match, you're done! That's the first letter that appears twice.
If you don't find a match after checking all the letters after the first one, move on to the second letter.
Repeat this process: compare the second letter to every letter that comes after it.
Keep doing this, moving one letter forward each time, until you find a match.

Code Implementation

def first_repeated_character_brute_force(input_string):
    string_length = len(input_string)
    for first_character_index in range(string_length):
        first_character = input_string[first_character_index]

        # Start from the next character to check for repetition.

        for second_character_index in range(first_character_index + 1, string_length):
            second_character = input_string[second_character_index]

            # Compare the first character with the characters after it.

            if first_character == second_character:
                return first_character

    # If no repeated character is found, return an empty string.

    return ''

Big(O) Analysis

Time Complexity

O(n²) – The given brute force approach involves iterating through the input string of length n. For each character, it compares it with all subsequent characters in the string to find a duplicate. In the worst-case scenario, each character will be compared with approximately n other characters. This nested comparison results in roughly n * (n-1)/2 comparisons which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm only uses a few integer variables to keep track of the indices during comparison. It does not create any auxiliary data structures like arrays, hash maps, or linked lists to store intermediate results or track visited characters. Therefore, the amount of extra memory used remains constant regardless of the input string's length (N). The space complexity is O(1), indicating constant space.

Optimal Solution

Approach

The key idea is to keep track of each letter we've seen. As soon as we find a letter we've seen before, we know that's the answer. This saves us from checking the entire word over and over.

Here's how the algorithm would work step-by-step:

Start with an empty memory or a blank slate to remember the letters we encounter.
Look at the very first letter in the word.
Check if this letter is in our memory. If it is, we've found the first letter that appears twice, and we're done.
If the letter is not in our memory, add it to our memory so we remember we've seen it.
Move on to the next letter in the word and repeat steps 3 and 4.
Continue this process until we find a repeated letter.

Code Implementation

def find_first_repeated_letter(input_string):
    seen_characters = set()

    for character in input_string:
        # Check if the current character has already been seen.
        if character in seen_characters:
            return character

        # If the character is not in seen_characters, add it.
        seen_characters.add(character)

        #After adding the char, continue

    # If no character is repeated, return None.
    return None

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input string of length n, examining each character once. For each character, we perform a constant-time check to see if it's already present in our set of seen characters. The number of iterations is directly proportional to the length of the input string, making the algorithm linear with respect to n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a data structure (described as "memory") to keep track of letters encountered. In the worst-case scenario, this "memory" will store all unique letters of the alphabet. Since the number of possible characters is bounded by the size of the alphabet (which is constant, regardless of the input string's length, N), the space required is also constant. Thus, the auxiliary space used is independent of the input string's size. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return an appropriate error value or throw an exception since there's no string to process.
String with only one character	Return an error or a special value like null, as a repeated character is impossible.
String with all identical characters	The first character is guaranteed to repeat as the second character, so return the first character.
Very long string approaching memory limits	Consider using a more memory-efficient data structure like a bit vector if the character set is small, or streaming the input if possible.
String contains only ASCII characters	Use an array of size 256 as a character set to optimize checking.
String contains Unicode characters outside basic ASCII	Use a hash map to track character counts for a larger character set.
String with no repeating characters	Return a specific value like null or an empty character to signify no repeating character found.
String with extremely long run of unique characters followed by a single repeating character	The solution may take longer to process due to iterating through the unique run, so consider optimizing for early termination if performance is critical.

Null or empty string input

How to Handle:

Return an appropriate error value or throw an exception since there's no string to process.

String with only one character

How to Handle:

Return an error or a special value like null, as a repeated character is impossible.

String with all identical characters

How to Handle:

The first character is guaranteed to repeat as the second character, so return the first character.

Very long string approaching memory limits

How to Handle:

Consider using a more memory-efficient data structure like a bit vector if the character set is small, or streaming the input if possible.

String contains only ASCII characters

How to Handle:

Use an array of size 256 as a character set to optimize checking.

String contains Unicode characters outside basic ASCII

How to Handle:

Use a hash map to track character counts for a larger character set.

String with no repeating characters

How to Handle:

Return a specific value like null or an empty character to signify no repeating character found.

String with extremely long run of unique characters followed by a single repeating character

How to Handle:

The solution may take longer to process due to iterating through the unique run, so consider optimizing for early termination if performance is critical.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of characters that the input string can contain? Is it limited to lowercase English letters, or can it include uppercase letters, numbers, or special characters?
If no character appears twice in the string, what should the function return? Should I return a specific character like null or an empty string, or throw an exception?
Is the input string guaranteed to be non-empty? What should I do if the input string is null or empty?
If there are multiple characters that appear twice, should I return the first one that appears twice in the string (as opposed to the first one to be repeated)?
Are there any constraints on the length of the input string?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first letter.
Compare it to every letter that comes after it in the set.
If you find a match, you're done! That's the first letter that appears twice.
If you don't find a match after checking all the letters after the first one, move on to the second letter.
Repeat this process: compare the second letter to every letter that comes after it.
Keep doing this, moving one letter forward each time, until you find a match.

Code Implementation

def first_repeated_character_brute_force(input_string):
    string_length = len(input_string)
    for first_character_index in range(string_length):
        first_character = input_string[first_character_index]

        # Start from the next character to check for repetition.

        for second_character_index in range(first_character_index + 1, string_length):
            second_character = input_string[second_character_index]

            # Compare the first character with the characters after it.

            if first_character == second_character:
                return first_character

    # If no repeated character is found, return an empty string.

    return ''

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The key idea is to keep track of each letter we've seen. As soon as we find a letter we've seen before, we know that's the answer. This saves us from checking the entire word over and over.

Here's how the algorithm would work step-by-step:

Start with an empty memory or a blank slate to remember the letters we encounter.
Look at the very first letter in the word.
Check if this letter is in our memory. If it is, we've found the first letter that appears twice, and we're done.
If the letter is not in our memory, add it to our memory so we remember we've seen it.
Move on to the next letter in the word and repeat steps 3 and 4.
Continue this process until we find a repeated letter.

Code Implementation

def find_first_repeated_letter(input_string):
    seen_characters = set()

    for character in input_string:
        # Check if the current character has already been seen.
        if character in seen_characters:
            return character

        # If the character is not in seen_characters, add it.
        seen_characters.add(character)

        #After adding the char, continue

    # If no character is repeated, return None.
    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return an appropriate error value or throw an exception since there's no string to process.
String with only one character	Return an error or a special value like null, as a repeated character is impossible.
String with all identical characters	The first character is guaranteed to repeat as the second character, so return the first character.
Very long string approaching memory limits	Consider using a more memory-efficient data structure like a bit vector if the character set is small, or streaming the input if possible.
String contains only ASCII characters	Use an array of size 256 as a character set to optimize checking.
String contains Unicode characters outside basic ASCII	Use a hash map to track character counts for a larger character set.
String with no repeating characters	Return a specific value like null or an empty character to signify no repeating character found.
String with extremely long run of unique characters followed by a single repeating character	The solution may take longer to process due to iterating through the unique run, so consider optimizing for early termination if performance is critical.

Null or empty string input

How to Handle:

Return an appropriate error value or throw an exception since there's no string to process.

String with only one character

How to Handle:

Return an error or a special value like null, as a repeated character is impossible.

String with all identical characters

How to Handle:

The first character is guaranteed to repeat as the second character, so return the first character.

Very long string approaching memory limits

How to Handle:

Consider using a more memory-efficient data structure like a bit vector if the character set is small, or streaming the input if possible.

String contains only ASCII characters

How to Handle:

Use an array of size 256 as a character set to optimize checking.

String contains Unicode characters outside basic ASCII

How to Handle:

Use a hash map to track character counts for a larger character set.

String with no repeating characters

How to Handle:

Return a specific value like null or an empty character to signify no repeating character found.

String with extremely long run of unique characters followed by a single repeating character

How to Handle:

The solution may take longer to process due to iterating through the unique run, so consider optimizing for early termination if performance is critical.