Problem Statement in English

You’re given a string s consisting of lowercase English letters and the characters '*', '#', and '%'. You need to process the string using the following operations:

  • If the current character is a lowercase English letter, append it to the result.
  • If the current character is '*', remove the last character from the result.
  • If the current character is '#', duplicate the entire result and append it to the end of the result.
  • If the current character is '%', reverse the entire result.

Return the final result after processing the entire string s.

Approach

We can use a stack to build the result string as we process each character in the input string s. The stack will allow us to easily perform the required operations based on the current character.

And we’re done!

Solution in Python


class Solution:
    def processStr(self, s: str) -> str:
        stack = []

        for c in s:
            if c.isalpha():
                stack.append(c)
            elif c == "*":
                if stack: stack.pop()
            elif c == "#":
                stack.extend(stack)
            else:
                stack = stack[::-1]

        return "".join(stack)

Complexity

  • Time: $O(n \cdot k)$
    Since we are iterating through the string once and each character might be processed multiple times depending on the operations. Here, k is the number of operations that can be applied to the string, which in the worst case can be proportional to the length of the string.

  • Space: $O(n)$
    Since in the worst case, we can have all characters in the stack.

And we are done.