medium Problem 8 Removing Stars From a String

Problem Statement

Given a string s, where * represents a star. We can remove a star along with its closest non-star character to its left in a single operation.

The task is to perform as many such operations as possible until all stars have been removed and return the resultant string.

Examples

Example 1

• Input: "abc*de*f"
• Expected Output: "abdf"
• Description: We remove c along with * to get "abde*f", then remove e along with * to get "abdf"

Example 2

• Input: "a*b*c*d"
• Expected Output: "d"
• Description: We remove a along with * to get "b*c*d", then remove b with * to get "c*d", then remove c with * to get "d".

Example 3

• Input: "abcd"
• Expected Output: "abcd"
• Description: As there is no *, the string remains the same.

Constraints:

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

Solution

To solve this problem, we can use a stack to efficiently handle the removal of characters caused by asterisks. As we iterate through the string, we push each non-asterisk character onto the stack. When we encounter an asterisk, we pop the top character from the stack, effectively removing the last non-asterisk character encountered. This process mimics the removal of characters as specified by the asterisks.

After processing the entire string, the remaining elements in the stack represent the characters that survived the removal process. Finally, we iterate through the stack to reconstruct the string in the correct order, as the stack will have the characters in reverse order of their original appearance.

Step-by-Step Algorithm

1. Initialization:

   • Create an empty stack to store characters.
   • The stack will help us manage the characters in the input string, especially when encountering a '*' character.

2. Iterate through each character in the input string:

   • Loop through the input string character by character.

3. Process each character:

   • If the character is '*':
     • Check if the stack is not empty:
       • If the stack has at least one character, pop the top character from the stack. This simulates removing the character preceding the '*'.
   • If the character is not '*':
     • Push the character onto the stack. This means we keep it in the final result.

4. Construct the final result string:

• After the iteration, convert the stack into a string by joining all elements in the revese order.

1. Return the final valid string.

Algorithm Walkthrough

1. Initialization:

   • Input string: "abc*de*f"
   • Stack: [] (empty)

2. Process each character:

   • Character 'a':
     • It is not a '*', so push 'a' onto the stack.
     • Stack: ['a']
   • Character 'b':
     • It is not a '*', so push 'b' onto the stack.
     • Stack: ['a', 'b']
   • Character 'c':
     • It is not a '*', so push 'c' onto the stack.
     • Stack: ['a', 'b', 'c']
   • Character '*':
     • It is a '*', and the stack is not empty, so pop the top character ('c') from the stack.
     • Stack: ['a', 'b']
   • Character 'd':
     • It is not a '*', so push 'd' onto the stack.
     • Stack: ['a', 'b', 'd']
   • Character 'e':
     • It is not a '*', so push 'e' onto the stack.
     • Stack: ['a', 'b', 'd', 'e']
   • Character '*':
     • It is a '*', and the stack is not empty, so pop the top character ('e') from the stack.
     • Stack: ['a', 'b', 'd']
   • Character 'f':
     • It is not a '*', so push 'f' onto the stack.
     • Stack: ['a', 'b', 'd', 'f']

3. Construct and return the final result string:

   • The final processed string is "abdf".

4. Return the final result:

   • The final processed string is "abdf".

Final Output:

• For the input "abc*de*f", the output after removing '*' and the preceding characters is "abdf".

Code

Here is how we can implement this algorithm:

import java.util.Stack;

public class Solution {

  // Method to remove '*' characters from a string
  public String removeStars(String s) {
    Stack<Character> stack = new Stack<>(); // Create a stack to store characters
    for (char c : s.toCharArray()) {
      // Loop through each character in the input string
      if (c == '*' && !stack.empty()) {
        // If the character is '*' and the stack is not empty
        stack.pop(); // Pop (remove) the top character from the stack
      } else if (c != '*') {
        // If the character is not '*'
        stack.push(c); // Push (add) the character to the stack
      }
    }

    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
      result.append(stack.pop());
    }
    return result.reverse().toString();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.removeStars("abc*de*f")); // Output: "abdf"
    System.out.println(solution.removeStars("a*b*c*d")); // Output: "d"
    System.out.println(solution.removeStars("abcd")); // Output: "abcd"
  }
}

Complexity Analysis

Time Complexity

• Processing the input string: The algorithm iterates through each character in the input string s. For each character, it performs either a push or pop operation on the stack, both of which take constant time, . Therefore, iterating over the string takes , where N is the length of the input string.

• Building the result string: Converting stack into the string takes time.

Overall time complexity: , where N is the length of the input string.

Space Complexity

• Stack space: The stack stores characters from the input string. In the worst case (when no * characters are present), the stack will contain all characters, which requires space.

• Result string space: The result string is used to store the final result which also takes space, as it holds the result of the same size as the input string (in the worst case).

Overall space complexity: .