Jobs

Interviews

Discussions

Delete Characters to Make Fancy String

Easy

Google

6 views

Topics:

Strings

A fancy string is a string where no three consecutive characters are equal.

Given a string s, delete the minimum possible number of characters from s to make it fancy.

Return the final string after the deletion. It can be shown that the answer will always be unique.

For example:

s = "leeetcode" should return "leetcode"
s = "aaabaaa" should return "aabaa"
s = "aab" should return "aab"

Write a function that takes a string as input and returns a fancy string.

What is the time and space complexity of your solution?

Delete Characters to Make Fancy String

Easy

Google

6 views

Topics:

Strings

A fancy string is a string where no three consecutive characters are equal.

Given a string s, delete the minimum possible number of characters from s to make it fancy.

Return the final string after the deletion. It can be shown that the answer will always be unique.

For example:

s = "leeetcode" should return "leetcode"
s = "aaabaaa" should return "aabaa"
s = "aab" should return "aab"

Write a function that takes a string as input and returns a fancy string.

What is the time and space complexity of your solution?

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 maximum possible length of the input string s?
Can the input string s be empty or null?
Does case matter when determining if three consecutive characters are the same? (e.g., should "aAA" be considered a fancy string?)
If there are multiple possible fancy strings after deleting characters, is any valid fancy string acceptable, or is there a specific criterion for selecting the "best" one?
Is the input string guaranteed to only contain alphanumeric characters?

Brute Force Solution

Approach

The brute force way to solve this is to try removing every possible combination of characters from the string. Then, for each of those combinations, we check if the resulting string is fancy according to the rules.

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

Start by considering removing no characters at all. This is one possibility.
Next, try removing just one character. Remove each character, one at a time, creating several new possibilities.
Then, try removing two characters. Again, try every possible pair of characters to remove.
Continue this pattern, removing three characters, then four, and so on, up to removing almost all the characters.
For each resulting string after removing some characters, check if it's a 'fancy string'. A fancy string never has three identical characters in a row.
If the string *is* fancy, keep it. If it's not, throw it away.
Finally, from all the fancy strings you've kept, pick the longest one. That's your answer!

Code Implementation

def delete_characters_to_make_fancy_string_brute_force(input_string):
    longest_fancy_string = ""
    string_length = len(input_string)

    # Iterate through all possible combinations of characters to remove
    for i in range(2 ** string_length):
        current_string = ""
        for j in range(string_length):
            # If the j-th bit of i is not set, keep the character
            if (i >> j) & 1 == 0:
                current_string += input_string[j]

        #Check if the resulting string is a fancy string
        if is_fancy(current_string):
            # Update the longest fancy string if the current one is longer
            if len(current_string) > len(longest_fancy_string):
                longest_fancy_string = current_string

    return longest_fancy_string

def is_fancy(test_string):
    if not test_string:
        return True

    count = 1
    for i in range(1, len(test_string)):
        # Reset count if characters are different
        if test_string[i] != test_string[i-1]:
            count = 1
        else:
            count += 1

        # Not fancy if 3 or more consecutive chars are the same
        if count >= 3:
            return False

    return True

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible subsets of the input string by considering removing each character or keeping it. This leads to 2^n possible combinations (subsets) of the string to evaluate. For each subset, checking if it is a fancy string takes O(n) time in the worst case, where n is the length of the original string, as we might need to iterate through the entire subset. Since we iterate through all subsets and evaluate each one, the total time complexity is O(n * 2^n) which is dominated by O(2^n).

Space Complexity

O(2^N) – The brute force approach explores all possible combinations of character removals. Each combination results in a new string being created and potentially stored for checking if it's a 'fancy string'. In the worst case, we could have nearly 2^N combinations to evaluate, each representing a potential fancy string, where N is the length of the input string. The length of each such string is, at most, N. Therefore, the space complexity is dominated by storing these potential 'fancy strings'. This means that the algorithm potentially stores a number of strings that scales exponentially with the input size (N).

Optimal Solution

Approach

The key idea is to go through the string once and remove extra characters to prevent having more than two of the same characters in a row. We build our fancy string character by character, making decisions based on the previous two characters.

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

Start with an empty fancy string.
Look at each character of the original string, one at a time.
For each character, check if it is the same as the last two characters we've added to the fancy string.
If it is the same, skip it; we don't want three in a row.
If it's different or if we don't have two characters in the fancy string yet, add it to the fancy string.
Keep going until you've checked all the characters in the original string.
The fancy string you've created is the answer.

Code Implementation

def make_fancy_string(input_string):
    fancy_string = ""

    for char in input_string:
        # Prevent more than two repeating chars
        if len(fancy_string) >= 2 and \
           char == fancy_string[-1] and \
           char == fancy_string[-2]:
            continue

        fancy_string += char

    return fancy_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of size n exactly once. Inside the loop, it performs a constant amount of work: comparing the current character to the last two characters of the result string and potentially appending the character to the result. Therefore, the time complexity is directly proportional to the length of the input string n, resulting in O(n).

Space Complexity

O(N) – The plain English explanation details constructing a 'fancy string' by appending characters. This fancy string is built character by character based on conditions from the original string. In the worst-case scenario, where no three consecutive characters in the original string are identical, the fancy string will have the same length as the original string. Thus, the auxiliary space required to store the fancy string grows linearly with the input size N, where N is the length of the original string.

Edge Cases

Case	How to Handle
Empty string	Return the empty string directly as it's already a fancy string.
String with one or two characters	Return the original string as these cases are inherently fancy strings.
String with three or more identical characters	Iterate and remove the extra characters exceeding the consecutive limit of two.
String with alternating characters (e.g., 'ababab')	The algorithm should leave these strings untouched, as they are already fancy.
String with long sequences of the same character (e.g., 'aaaaabbbb')	The algorithm must correctly reduce each sequence to a maximum of two repeating characters.
Maximum length string consisting of repeating characters	Ensure the algorithm scales efficiently to handle large strings without excessive time complexity.
String with mixed sequences of repeating and alternating characters.	The algorithm must handle the repeating and alternating character conditions simultaneously.
String consisting of only 2 repeating characters	Return the input string as no removal is needed.

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 maximum possible length of the input string s?
Can the input string s be empty or null?
Does case matter when determining if three consecutive characters are the same? (e.g., should "aAA" be considered a fancy string?)
If there are multiple possible fancy strings after deleting characters, is any valid fancy string acceptable, or is there a specific criterion for selecting the "best" one?
Is the input string guaranteed to only contain alphanumeric characters?

Brute Force Solution

Approach

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

Start by considering removing no characters at all. This is one possibility.
Next, try removing just one character. Remove each character, one at a time, creating several new possibilities.
Then, try removing two characters. Again, try every possible pair of characters to remove.
Continue this pattern, removing three characters, then four, and so on, up to removing almost all the characters.
For each resulting string after removing some characters, check if it's a 'fancy string'. A fancy string never has three identical characters in a row.
If the string *is* fancy, keep it. If it's not, throw it away.
Finally, from all the fancy strings you've kept, pick the longest one. That's your answer!

Code Implementation

def delete_characters_to_make_fancy_string_brute_force(input_string):
    longest_fancy_string = ""
    string_length = len(input_string)

    # Iterate through all possible combinations of characters to remove
    for i in range(2 ** string_length):
        current_string = ""
        for j in range(string_length):
            # If the j-th bit of i is not set, keep the character
            if (i >> j) & 1 == 0:
                current_string += input_string[j]

        #Check if the resulting string is a fancy string
        if is_fancy(current_string):
            # Update the longest fancy string if the current one is longer
            if len(current_string) > len(longest_fancy_string):
                longest_fancy_string = current_string

    return longest_fancy_string

def is_fancy(test_string):
    if not test_string:
        return True

    count = 1
    for i in range(1, len(test_string)):
        # Reset count if characters are different
        if test_string[i] != test_string[i-1]:
            count = 1
        else:
            count += 1

        # Not fancy if 3 or more consecutive chars are the same
        if count >= 3:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with an empty fancy string.
Look at each character of the original string, one at a time.
For each character, check if it is the same as the last two characters we've added to the fancy string.
If it is the same, skip it; we don't want three in a row.
If it's different or if we don't have two characters in the fancy string yet, add it to the fancy string.
Keep going until you've checked all the characters in the original string.
The fancy string you've created is the answer.

Code Implementation

def make_fancy_string(input_string):
    fancy_string = ""

    for char in input_string:
        # Prevent more than two repeating chars
        if len(fancy_string) >= 2 and \
           char == fancy_string[-1] and \
           char == fancy_string[-2]:
            continue

        fancy_string += char

    return fancy_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	Return the empty string directly as it's already a fancy string.
String with one or two characters	Return the original string as these cases are inherently fancy strings.
String with three or more identical characters	Iterate and remove the extra characters exceeding the consecutive limit of two.
String with alternating characters (e.g., 'ababab')	The algorithm should leave these strings untouched, as they are already fancy.
String with long sequences of the same character (e.g., 'aaaaabbbb')	The algorithm must correctly reduce each sequence to a maximum of two repeating characters.
Maximum length string consisting of repeating characters	Ensure the algorithm scales efficiently to handle large strings without excessive time complexity.
String with mixed sequences of repeating and alternating characters.	The algorithm must handle the repeating and alternating character conditions simultaneously.
String consisting of only 2 repeating characters	Return the input string as no removal is needed.