Jobs

Interviews

Discussions

Lexicographically Minimum String After Removing Stars

Medium

Asked by:

More companies

28 views

Topics:

ArraysStringsStacks

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', do the following operation:

Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

Example 1:

Input: s = "aaba*"

Output: "aab"

Explanation:

We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.

Example 2:

Input: s = "abc"

Output: "abc"

Explanation:

There is no '*' in the string.

Constraints:

1 <= s.length <= 10⁵
s consists only of lowercase English letters and '*'.
The input is generated such that it is possible to delete all '*' characters.

Try coding it in LeetCode

Lexicographically Minimum String After Removing Stars

Medium

Asked by:

28 views

Topics:

ArraysStringsStacks

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', do the following operation:

Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

Example 1:

Input: s = "aaba*"

Output: "aab"

Explanation:

We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.

Example 2:

Input: s = "abc"

Output: "abc"

Explanation:

There is no '*' in the string.

Constraints:

1 <= s.length <= 10⁵
s consists only of lowercase English letters and '*'.
The input is generated such that it is possible to delete all '*' characters.

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 characters are allowed in the input string, beyond the lowercase English letters and '*'? Should I expect only lowercase letters and asterisks?
If multiple lexicographically smallest strings are possible after removing all '*', which one should I return?
Can the input string be empty or null? If so, what should the output be?
Is there a maximum length for the input string?
How do I handle consecutive '*' characters? Should they be treated independently or as a single unit?

Brute Force Solution

Approach

The brute force way to solve this is to try out all possible ways to remove characters according to the rules, and then find the best result. We generate every possible string we can make by applying the star removal rule, and then compare them all.

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

Consider all possible combinations of applying the star removal rule (a star removes the character immediately to the left).
For each of these combinations, build the resulting string by actually performing the removals.
Once you have all the possible resulting strings, compare them against each other.
The string that comes first alphabetically is your answer. If you find multiple strings that are the same and come first, just pick one of them.

Code Implementation

def lexicographically_minimum_string_after_removing_stars_brute_force(input_string):
    possible_strings = []

    def generate_strings(current_string, index):
        if index == len(input_string):
            possible_strings.append(current_string)
            return

        # Option 1: Don't remove anything at this index
        generate_strings(current_string + input_string[index], index + 1)

        # Option 2: Remove a character if possible
        if input_string[index] == '*' and current_string:
            generate_strings(current_string[:-1], index + 1)
        elif input_string[index] == '*' and not current_string:
            #Do not allow the removal if there is no character to remove
            generate_strings(current_string, index + 1)

    generate_strings("", 0)

    # Find the lexicographically smallest string
    minimum_string = None

    #Compare all the generated strings to find the smallest
    for possible_string in possible_strings:
        if minimum_string is None or possible_string < minimum_string:
            minimum_string = possible_string

    return minimum_string

Big(O) Analysis

Time Complexity

O(2^n * n) – The core of the brute-force approach lies in exploring all possible combinations of applying the star removal rule. For a string of length n, there can be up to n/2 star characters. Each star can either be used to remove a preceding character or not, leading to a maximum of 2^(n/2) possible combinations. For each of these combinations, building the resulting string by performing the removals takes O(n) time in the worst case. Comparing the strings does not change the overall complexity. Therefore, the overall time complexity is O(2^(n/2) * n), which can be simplified to O(2^n * n) as 2^(n/2) is still exponential, and the constant factor of n does not change the exponential order.

Space Complexity

O(2^N) – The brute force approach explores all possible combinations of applying the star removal rule. In the worst-case scenario, each character might have a corresponding removal decision (to remove or not remove the character to its left). Therefore, we can generate up to 2^N possible strings, where N is the length of the input string. Each generated string takes up memory proportional to its length, which can be up to N. Storing all these strings requires space proportional to N * 2^N. Comparing all of the strings would take constant space. Therefore the space complexity is O(2^N).

Optimal Solution

Approach

The key is to process the string in reverse. We use a special storage area to keep track of characters that might be part of our final, best string. This avoids unnecessary checks and leads us directly to the smallest possible string.

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

Start by looking at the string from the very end.
Imagine a temporary storage area where we will keep potentially good characters.
As we go backwards, if we see a regular letter, we add it to our storage.
If we see a 'star', we need to remove the last letter we put in the storage (if there is one).
Keep doing this until we reach the beginning of the string.
Now, take all the letters left in the storage area and reverse their order. This is our final, smallest string.

Code Implementation

def lexicographically_minimum_string_after_removing_stars(input_string):
    potential_characters = []
    
    for i in range(len(input_string) - 1, -1, -1):
        current_character = input_string[i]

        if current_character == '*':
            # Remove last char if star is encountered
            if potential_characters:
                potential_characters.pop()

        else:
            # Add non-star chars to possible solution
            potential_characters.append(current_character)

    # Reverse the order to get lexicographically smallest
    potential_characters.reverse()

    return ''.join(potential_characters)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once, from right to left. Inside the loop, it performs constant time operations such as adding or removing characters from the temporary storage. Reversing the storage content at the end also takes O(k) where k is the length of storage and k <= n, which is O(n) in the worst case. Therefore, the dominant operation is the single pass through the string, resulting in a time complexity of O(n).

Space Complexity

O(N) – The provided solution utilizes a temporary storage area to hold characters. In the worst-case scenario, where there are no star characters, this storage area will need to accommodate all N characters from the input string. Therefore, the auxiliary space required grows linearly with the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately as there's nothing to process.
String with only stars	Return an empty string after removing all stars and preceding characters.
String with no stars	Return the original string as is, since no removal is needed.
String with consecutive stars	Process each star independently, potentially removing multiple characters back-to-back.
Stars at the beginning of the string	The code should ignore stars at the beginning as there are no characters to remove before them.
Large input string (performance implications)	The solution should use a stack-based or string builder approach for efficient character manipulation and avoid excessive string copying for performance on large inputs.
String with characters appearing after the last star	Ensure that only the part of the string up to and including the last effective star is processed, characters after that should be discarded.
All characters are identical except for stars	The algorithm correctly handles a string with repeating characters and selectively removes them if followed by stars, resulting in either an empty or single character string.

Empty string input

How to Handle:

Return an empty string immediately as there's nothing to process.

String with only stars

How to Handle:

Return an empty string after removing all stars and preceding characters.

String with no stars

How to Handle:

Return the original string as is, since no removal is needed.

String with consecutive stars

How to Handle:

Process each star independently, potentially removing multiple characters back-to-back.

Stars at the beginning of the string

How to Handle:

The code should ignore stars at the beginning as there are no characters to remove before them.

Large input string (performance implications)

How to Handle:

The solution should use a stack-based or string builder approach for efficient character manipulation and avoid excessive string copying for performance on large inputs.

String with characters appearing after the last star

How to Handle:

Ensure that only the part of the string up to and including the last effective star is processed, characters after that should be discarded.

All characters are identical except for stars

How to Handle:

The algorithm correctly handles a string with repeating characters and selectively removes them if followed by stars, resulting in either an empty or single character string.

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 characters are allowed in the input string, beyond the lowercase English letters and '*'? Should I expect only lowercase letters and asterisks?
If multiple lexicographically smallest strings are possible after removing all '*', which one should I return?
Can the input string be empty or null? If so, what should the output be?
Is there a maximum length for the input string?
How do I handle consecutive '*' characters? Should they be treated independently or as a single unit?

Brute Force Solution

Approach

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

Consider all possible combinations of applying the star removal rule (a star removes the character immediately to the left).
For each of these combinations, build the resulting string by actually performing the removals.
Once you have all the possible resulting strings, compare them against each other.
The string that comes first alphabetically is your answer. If you find multiple strings that are the same and come first, just pick one of them.

Code Implementation

def lexicographically_minimum_string_after_removing_stars_brute_force(input_string):
    possible_strings = []

    def generate_strings(current_string, index):
        if index == len(input_string):
            possible_strings.append(current_string)
            return

        # Option 1: Don't remove anything at this index
        generate_strings(current_string + input_string[index], index + 1)

        # Option 2: Remove a character if possible
        if input_string[index] == '*' and current_string:
            generate_strings(current_string[:-1], index + 1)
        elif input_string[index] == '*' and not current_string:
            #Do not allow the removal if there is no character to remove
            generate_strings(current_string, index + 1)

    generate_strings("", 0)

    # Find the lexicographically smallest string
    minimum_string = None

    #Compare all the generated strings to find the smallest
    for possible_string in possible_strings:
        if minimum_string is None or possible_string < minimum_string:
            minimum_string = possible_string

    return minimum_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by looking at the string from the very end.
Imagine a temporary storage area where we will keep potentially good characters.
As we go backwards, if we see a regular letter, we add it to our storage.
If we see a 'star', we need to remove the last letter we put in the storage (if there is one).
Keep doing this until we reach the beginning of the string.
Now, take all the letters left in the storage area and reverse their order. This is our final, smallest string.

Code Implementation

def lexicographically_minimum_string_after_removing_stars(input_string):
    potential_characters = []
    
    for i in range(len(input_string) - 1, -1, -1):
        current_character = input_string[i]

        if current_character == '*':
            # Remove last char if star is encountered
            if potential_characters:
                potential_characters.pop()

        else:
            # Add non-star chars to possible solution
            potential_characters.append(current_character)

    # Reverse the order to get lexicographically smallest
    potential_characters.reverse()

    return ''.join(potential_characters)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately as there's nothing to process.
String with only stars	Return an empty string after removing all stars and preceding characters.
String with no stars	Return the original string as is, since no removal is needed.
String with consecutive stars	Process each star independently, potentially removing multiple characters back-to-back.
Stars at the beginning of the string	The code should ignore stars at the beginning as there are no characters to remove before them.
Large input string (performance implications)	The solution should use a stack-based or string builder approach for efficient character manipulation and avoid excessive string copying for performance on large inputs.
String with characters appearing after the last star	Ensure that only the part of the string up to and including the last effective star is processed, characters after that should be discarded.
All characters are identical except for stars	The algorithm correctly handles a string with repeating characters and selectively removes them if followed by stars, resulting in either an empty or single character string.

Empty string input

How to Handle:

Return an empty string immediately as there's nothing to process.

String with only stars

How to Handle:

Return an empty string after removing all stars and preceding characters.

String with no stars

How to Handle:

Return the original string as is, since no removal is needed.

String with consecutive stars

How to Handle:

Process each star independently, potentially removing multiple characters back-to-back.

Stars at the beginning of the string

How to Handle:

The code should ignore stars at the beginning as there are no characters to remove before them.

Large input string (performance implications)

How to Handle:

The solution should use a stack-based or string builder approach for efficient character manipulation and avoid excessive string copying for performance on large inputs.

String with characters appearing after the last star

How to Handle:

Ensure that only the part of the string up to and including the last effective star is processed, characters after that should be discarded.

All characters are identical except for stars

How to Handle:

The algorithm correctly handles a string with repeating characters and selectively removes them if followed by stars, resulting in either an empty or single character string.