Removing Stars From a String

#249 Most AskedMedium

Removing Stars From a String #249 Most Asked

Medium

Goldman Sachs

4 views

Topics:

StringsStacks

You are given a string s, which contains stars *.

In one operation, you can:

Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note:

The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.

Example 1:

Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1^st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2^nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3^rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

Example 2:

Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters and stars *.
The operation above can be performed on s.

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 maximum length of the input string 's'?
If there are multiple non-star characters to the left of a star at the same distance, which one should be removed?
If there are stars at the beginning of the string with no non-star characters to their left, how should those stars be handled?
Can the input string be empty or null?
Can the string contain characters other than lowercase English letters and asterisks?

Brute Force Solution

Approach

The brute force approach to removing stars from a string is like trying out every possible removal combination. For each star, we consider both removing it and the character to its left, or not removing them at all, and checking if the resulting string is valid.

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

Look at the string from left to right, one character at a time.
When you see a star, you have two choices: either remove the star and the character before it, or don't remove anything.
Try out the first choice: remove the star and the character before it, and then continue looking at the rest of the string, making the same choices when you find more stars.
Make a copy of the string *without* the deleted characters. Note that for strings with many stars this could lead to many copies!
Once you reach the end of the string and there are no more stars, you have one possible solution. Note what it looks like.
Now, go back to the very first star you saw, and instead of removing it and the character before it, try the second choice: don't remove anything at all. The string copy will look different than before.
Again, continue looking at the rest of the string, making the same choices when you find other stars.
Once you reach the end of the string and there are no more stars, you have another possible solution. Note what *this* one looks like too.
Keep doing this, going back to each star and trying both choices (remove or don't remove), until you've explored every possible combination of removals.
At the end, you will have looked at all possibilities; pick the correct string among the generated strings.

Code Implementation

def remove_stars_brute_force(input_string):
    possible_results = []

    def backtrack(current_string, index):
        if index == len(current_string):
            possible_results.append(
                ''.join(current_string)
            )
            return

        if current_string[index] == '*':
            # Try removing the star and the character before it
            if index > 0:
                character_before_star =
                    current_string[index - 1]
                index_before_star = index - 1

                temp_string = current_string[:index-1] + current_string[index+1:]

                backtrack(temp_string, 0)

            # Try not removing the star
            temp_string = current_string[:index] + current_string[index+1:]
            backtrack(temp_string, 0)

        else:
            # move to the next character
            backtrack(current_string, index + 1)

    backtrack(list(input_string), 0)
    result = []
    for possibility in possible_results:
        is_valid = True
        string_without_stars = ""

        string_index = 0
        while string_index < len(possibility):

            if possibility[string_index] == '*':
                is_valid = False
                break
            else:
                string_without_stars +=
                    possibility[string_index]

            string_index += 1
        if is_valid:
            result.append(string_without_stars)

    # We explored all possibilities
    if not result:
        return ''

    # Return one valid string
    return result[0]

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible combinations of removing or not removing each star and its preceding character. In the worst case, every character in the input string 'n' could be a star. For each star, there are two choices: remove it and the character to its left or do nothing. This binary choice for each star leads to 2 * 2 * ... * 2 (n times) possibilities which translates to 2^n. Therefore, the time complexity grows exponentially with the size of the input string.

Space Complexity

O(2^N) – The brute force approach explores every possible combination of removing or not removing a star and the preceding character. For each star encountered, a copy of the string (or a modified version of it) is created to explore the removal and non-removal options. In the worst-case scenario, where there are many stars in the string, each star potentially doubles the number of string copies being stored, creating a branching factor of 2 for each star. Therefore, the number of copies and the space required grow exponentially with the number of stars, N, leading to a space complexity of O(2^N), where N is the number of characters in the input string.

Optimal Solution

Approach

The efficient way to solve this problem is to go through the string one character at a time, keeping track of which characters to keep. When we see a star, we remove the previous character; otherwise, we keep the current character. At the end, we have the cleaned-up string.

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

Start with an empty collection of characters that we will keep.
Look at each character in the string one at a time, from left to right.
If the current character is NOT a star, add it to our collection of kept characters.
If the current character IS a star, and there are any characters in the collection we are keeping, remove the last character we added to the collection.
Repeat steps 2-4 until we have looked at every character in the original string.
The characters that remain in our collection are the characters in the final string, in the correct order.

Code Implementation

def remove_stars_from_string(input_string):
    kept_characters = []

    for character in input_string:
        if character != '*':
            # Add non-star characters to the list
            kept_characters.append(character)

        else:
            # Remove last character if it's not empty
            if kept_characters:
                kept_characters.pop()

    return "".join(kept_characters)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n exactly once. Inside the loop, the operations performed (checking for a star and either adding or removing an element from the character collection) take constant time, O(1). Therefore, the overall time complexity is directly proportional to the length of the string, resulting in a time complexity of O(n).

Space Complexity

O(N) – The algorithm uses a collection (implicitly a list or string builder) to store the characters that are kept. In the worst-case scenario, where there are no star characters in the input string of length N, all N characters will be added to this collection. Therefore, the auxiliary space used is proportional to the size of the input string, N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string since there are no characters to process.
String containing only stars	Return an empty string as all characters will be removed.
String containing no stars	Return the original string as no removal operations are needed.
String starting with a star	The stack approach avoids adding characters when stars are encountered without a preceding non-star character.
Consecutive stars in the string	The algorithm correctly handles consecutive stars, removing characters for each star encountered.
String with many stars at the end	The stack approach efficiently handles this scenario without errors.
Maximum string length (e.g., 10^5) with interleaved characters and stars.	The stack-based solution provides O(n) time complexity, suitable for large inputs.
Input with special characters other than lowercase letters and asterisks.	The problem description constrains to lowercase and asterisk, so add input validation to ignore/reject other characters.

Null or empty input string

How to Handle:

Return an empty string since there are no characters to process.

String containing only stars

How to Handle:

Return an empty string as all characters will be removed.

String containing no stars

How to Handle:

Return the original string as no removal operations are needed.

String starting with a star

How to Handle:

The stack approach avoids adding characters when stars are encountered without a preceding non-star character.

Consecutive stars in the string

How to Handle:

The algorithm correctly handles consecutive stars, removing characters for each star encountered.

String with many stars at the end

How to Handle:

The stack approach efficiently handles this scenario without errors.

Maximum string length (e.g., 10^5) with interleaved characters and stars.

How to Handle:

The stack-based solution provides O(n) time complexity, suitable for large inputs.

Input with special characters other than lowercase letters and asterisks.

How to Handle:

The problem description constrains to lowercase and asterisk, so add input validation to ignore/reject other characters.