Problem URL: Decode string

We will use a stack and append the values until we reach ]. Then we pop the values from stack and make a string until we reach [. Then we pop the numbers from the stack and multiply it with the string and push it back to the stack. We will do it till the end of the input string. Finally we merge everything from the stack to a string and return that as our result.

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

        for i in range(len(s)):
            if s[i] != ']':
                stack.append(s[i])
            else:
                curStr = ''
                while stack[-1] != '[':
                    curStr = stack.pop() + curStr
                stack.pop()

                num = ''
                while stack and stack[-1].isdigit():
                    num = stack.pop() + num

                stack.append(int(num) * curStr)

        return "".join(stack)

Time Complexity: O(n)
Space Complexity: O(n)