Expand a nested run-length encoded string

Question

A compact encoding writes k[substring] to mean the substring repeated k times, and these can nest. Decode the full string. Return the fully expanded string. Repeat counts can be multi-digit; nesting can be arbitrarily deep.

Accepted Answer

Use two stacks: one for pending repeat counts, one for the string built so far before each [. Scan characters: digits accumulate into a number; [ pushes the current count and current buffer, then resets them; ] pops the count and the saved buffer, appends the current buffer repeated that many times back onto the saved buffer, and makes that the new current buffer. Plain letters append to the current buffer. Tracing "2[a3[b]]": the inner 3[b] builds "bbb", giving "abbb", and the outer 2[...] doubles it to "abbbabbb". Time O(length of the output), space O(nesting depth + output). Edge cases: mu…

Expand a nested run-length encoded string

Your answer

More Coding questions