Problem statement

https://binarysearch.com/problems/String-Expansion/

Solution

Equal to Leetcode 0394. Decode String.

Complexity

It is O(m) for time and space, where m is the length of final answer.

Code

class Solution:
    def solve(self, s):
        it, num, stack = 0, 0, [""]
        while it < len(s):
            if s[it].isdigit():
                num = num * 10 + int(s[it])
            elif s[it] == "(":
                stack.append(num)
                num = 0
                stack.append("")
            elif s[it] == ")":
                str1 = stack.pop()
                rep = stack.pop()
                str2 = stack.pop()
                stack.append(str2 + str1 * rep)
            else:
                stack[-1] += s[it]              
            it += 1           
        return "".join(stack)