The problem
Decode a string where k[text] means “text repeated k times”, possibly nested.
Input: "3[a2[c]]" Output: "accaccacc"
Picture it
Picture nested gift boxes: each says how many copies of its contents to make. Opening a box ([) puts what we had so far and the repeat count on a stack. Closing it (]) repeats the inner text and glues it back onto what we saved.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Stack of (previous text, count). O(output length).
Python solution
def decode(s):
stack, cur, k = [], "", 0
for ch in s:
if ch.isdigit():
k = k * 10 + int(ch)
elif ch == "[":
stack.append((cur, k))
cur, k = "", 0
elif ch == "]":
prev, times = stack.pop()
cur = prev + cur * times
else:
cur += ch
return curIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.