Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Optional Practice: Removing Stars From a String (medium)

This problem is optional practice. It is the same idea as Balanced Parentheses and Remove All Adjacent Duplicates earlier in the chapter: scan the string once, and pop the stack when the top cancels with what you are looking at. Work through it for a third repetition of that pattern, or skip it and carry on.

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.

.....

.....

.....

Like the course? Get enrolled and start learning!
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] ===
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

Show 1 reply
E

ethanedge

· 3 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 2 replies
J

jcheenatcode

· 3 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 2 replies
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 2 replies

Reading Progress

0%

Vote for new content