LeetCode 394 Decode String - Example and Complexity Analysis

Trace "3[a2[c]]".

Initialize: countStack = [], stringStack = [], currString = "", currNum = 0.

Read "3": currNum = 3.

Read "[": push 3 and "" to stacks. Reset: currString = "", currNum = 0.

Read "a": currString = "a".

Read "2": currNum = 2.

Read "[": push 2 and "a" to stacks. Reset: currString = "", currNum = 0.

Read "c": currString = "c".

Read "]": pop 2 and "a". currString = "a" + "c" * 2 = "acc".

Read "]": pop 3 and "". currString = "" + "acc" * 3 = "accaccacc".

Single pass. $O(n)$ time where $n$ is output length. Stack depth equals nesting depth. $O(m)$ space where $m$ is max nesting.