Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Problem 8: Removing Stars From a String (medium)

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 `*

.....

.....

.....

Like the course? Get enrolled and start learning!
J

jcheenatcode

· 2 years ago

There are no instructions given when there is nothing to the left of a . Like in case abcd the first * has no non-star to the left of it.

Show 1 reply
E

ethanedge

· 2 years ago

Does this bit of code violate what it means to be a stack?

        StringBuilder sb = new StringBuilder(); // Create a StringBuilder to build the result string
        for (char c : stack) { // Iterate through the characters in the stack
            sb.append(c); // Append each character to the StringBuilder
        }
        return sb.toString(); // Convert the StringBuilder to a string and return the result

As it is iterating from bottom to top, it's no longer LIFO.

Show 1 reply
R

reagankm

· 2 years ago

Same as the last problem. The solution talks about popping from the stack and then reversing the string to get stuff in the right order. The Java implementation sidesteps this by using a for loop to access the stack elements so no reverse is needed

V

venkatlearning11

· 3 years ago

Not required pop and stack for this problem, because if you do below condition that would remove start right?

for (char c : s.toCharArray()) { // Loop through each character in the input string
    if (c != '*') { // If the character is not '*'
        stack.push(c); // Push (add) the character to the stack
    }
}
Show 1 reply
tai

tai

· 2 years ago

This one was a bit tricky for me because I didn't think of the scenario where you could have two *s next to each other, initially I was using a boolean to keep track of the * as I iterated, but if you have two *s next to each other, this doesn't work. I eventually settled on just counting the *s as I went, and decrementing as I encountered non-star characters, this way you don't need to do any reversing. I don't know why they keep proposing that as a viable solution, I feel like in most interviews you'd get dinged for it, or at least it'd be a strange solution if you're limited to using a stack.

class Solution {
removeStars(s) {
    // ToDo: Write Your Code Here.
    const stack = []
    let starCount = 0;
    for (let i = s.length - 1; i > -1; i--) {
        if (s[i] ===