stack

Question 1

Removing Stars From a String
code

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 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd 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.

Answer 1

def removeStars(s: str) -> str:
    stack = collections.deque()
    for char in s:
        if char != '*':
            stack.append(char)
        else:
            stack.pop()
    return "".join(stack)

Question 2

Removing stars from a string
algorithm

Answer 2

1. Initialize a stack of characters st.
2. Iterate over the string s from the start and for each index i of the string:
   
   • If s[i] == '*', we perform the pop operation to remove the top character from the stack.
   • Otherwise, we have a non-star character, so we push it into the stack.
3. Create an empty string variable answer.
4. While the stack is not empty:
   
   • Append the top character of the stack to answer and remove it from the stack.
5. Return the reverse of answer.

Question 3

asteroid collision
intuition

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Answer 3

The core idea is to use a stack to keep track of right-moving asteroids.

Iterate through the asteroids:

1. Right-moving asteroids (positive values) are added to the stack because they might collide with left-moving asteroids that come later.
2. Left-moving asteroids (negative values) check for collisions immediately with the top of the stack:
   - If they destroy the right-moving asteroid, continue checking with the next.
   - If they are destroyed or both explode, stop and don’t add the left-moving asteroid to the stack.

Question 4

asteroid collision
code

Answer 4

def asteroidCollision(asteroids: List[int]) -> List[int]:
    stack = []
    for a in asteroids:
        while stack and a < 0 < stack[-1]:
            if stack[-1] < -a:
                stack.pop() # The right-moving asteroid explodes
                continue
            elif stack[-1] == -a:
                stack.pop() # Both asteroids explode
            break
        else:
            stack.append(a)
    return stack

Question 5

decode string
intuition

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

Answer 5

1. Keep Adding to stack until we see a closing bracket ‘]’.
2. If we see a closing bracket, pop stack until we see a opening bracket ‘[’.
3. Pop the Opening bracket, get the number to be multiplied with, use while loop since number can be multidigit.
4. Multiply the string with the extracted number and append back to the stack in case of nested brackets. Continue until end of string.
5. Join all the elements of the stack list.

Question 6

decode string
code

Answer 6

def decodeString(s: str) -> str:
    stack = []

    for char in s:
        ## Keep adding to Stack until a ']'
        if char != "]":
            stack.append(char)
            
        else: 
            ## Extracting SubString to be Multiplied
            curr_str = ""
            while stack[-1] != "[":
                curr_str = stack.pop() + curr_str
            ## Pop to remove '['
            stack.pop()

            ## Extract full number (handles multi-digit, e.g. 10)
            curr_num = ""
            while stack and stack[-1].isdigit():
                curr_num = stack.pop() + curr_num
            
            ## Updating Stack with multiplied string
            curr_str = int(curr_num) * curr_str
            stack.append(curr_str)

    return "".join(stack)