medium Removing Stars From a String

Problem Statement

You have a string s that contains lowercase letters and stars *.

In single operation:

• Choose any star in the string s.
• Each star removes the closest letter to its left along with itself.

Return the resultant string after performing all such operations.

Note:- Each star will have a corresponding letter to remove.

Examples

Example 1

• Input: s = "ab*cd*ef*"
• Expected Output: "ace"
• Justification: First, remove b and *, resulting in "acd*ef*". Next, remove d and *, resulting in "acef*". Finally, remove f and *, resulting in "ace".

Example 2

• Input: s = "a*bc*def**g"
• Expected Output: "bdg"
• Justification: First, remove a and *, resulting in "bc*def**g". Next, remove c and *, resulting in "bdef**g". Then, remove f and *, resulting in "bde*g". Finally, remove e and *, resulting in "bdg".

Example 3

• Input: s = "xy*z*ww*"
• Expected Output: "xw"
• Justification: First, remove y and *, resulting in "xz*ww*". Next, remove z and *, resulting in "xww*". Finally, remove w and *, resulting in "xw".

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'll use a stack to simulate the removal process. The stack will help us keep track of characters that haven't been removed yet. When we encounter a star *, we remove the top character from the stack, as it represents the closest letter to the left. This approach is effective because it directly mimics the described removal process, ensuring we handle each star in the correct order.

The stack-based simulation approach ensures that each star removes the correct character in time complexity, where n is the length of the string. This is the most efficient way to handle the problem since it processes each character only once.

Step-by-step Algorithm

1. Initialize the Stack:

   • Use StringBuilder stack to simulate stack operations.

2. Iterate Through the String:

   • For each character c in the string s:
     • If c is not '*':
       • Push c to stack.
     • Else (if c is '*'):
       • Remove the top character from stack as we need to remove the nearest character from the left whenever the * character is encountered.

3. Return the Result:

   • Convert stack to a string and return the resultant string.

Algorithm Walkthrough

Let's consider the input: s = "abcdef*"

• Step 1: Initialize an empty stack: [].
• Step 2: Process characters:
  • a -> stack: ['a']
  • b -> stack: ['a', 'b']
  • * -> pop b -> stack: ['a']
  • c -> stack: ['a', 'c']
  • d -> stack: ['a', 'c', 'd']
  • * -> pop d -> stack: ['a', 'c']
  • e -> stack: ['a', 'c', 'e']
  • f -> stack: ['a', 'c', 'e', 'f']
  • * -> pop f -> stack: ['a', 'c', 'e']
• Step 3: Join stack to form the result: "ace".

Code

public class Solution {

  public String removeStars(String s) {
    // Use StringBuilder as a stack
    StringBuilder stack = new StringBuilder();

    // Iterate through each character in the string
    for (char c : s.toCharArray()) {
      if (c != '*') {
        // If character is not '*', push it onto the stack
        stack.append(c);
      } else {
        // If character is '*', pop the top character from the stack
        stack.deleteCharAt(stack.length() - 1);
      }
    }

    // Convert stack to string
    return stack.toString();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.removeStars("ab*cd*ef*")); // Output: "ace"
    System.out.println(solution.removeStars("a*bc*def**g")); // Output: "bdg"
    System.out.println(solution.removeStars("xy*z*ww*")); // Output: "xw"
  }
}

Complexity Analysis

• Time Complexity: - We process each character of the string exactly once.
• Space Complexity: - In the worst case, the stack may store all characters of the string.

🎯 STRICT STANDOUT — Solution Removing Stars From a String

0. Why this page exists

Family: Stack string collapse

Locks O(n) vs O(n²) rebuild and hand-runs multi-star collapses so learners feel amortized pops.

1. Pattern + when-NOT (K12)

Pattern / template: stack=[]; for c in s: if c!='*': stack.append(c) else: stack.pop(). return ''.join(stack).

When-NOT: When-NOT if stars can appear without left letter (guard empty). When-NOT balanced bracket validation (types + order). Prefer two-pointer if interview forbids aux list.

2. Complexity derivation (K11)

Time O(n): each char once; join O(n).
Space O(n) worst (no stars).
Not O(n log n) — no sorting of characters.

3. Edge hand-run (K13)

"ab*cd*ef*" → stack path: a,b,pop→a,c,d,pop→ac,e,f,pop→ace.
"a*" → "". "abc" no stars → "abc".
Guarantee: operation always valid so pop never on empty.

4. Interviewer follow-ups & drills

Q1. Amortized cost of pops?
Model answer: Each letter pushed once and popped at most once → total O(n).

Q2. Relate to Validate Stack Sequences?
Model answer: Both are LIFO simulations; here ops are inline in one string.

Q3. StringBuilder vs stack of chars?
Model answer: Same asymptotics; careful with language string immutability.