Two stacks: counts and strings. Push on [, pop and repeat on ].
function decodeString(s): countStack = [] stringStack = [] currString = "" currNum = 0 for char in s: if char.isdigit(): currNum = currNum * 10 + int(char) elif char == '[': countStack.push(currNum) stringStack.push(currString) currString = "" currNum = 0 elif char == ']': count = countStack.pop() prevString = stringStack.pop() currString = prevString + currString * count else: currString += char return currString
time, space for stack depth.