awelgorithms

Decode a nested repeat string

Updated

For strings like "3[ab]2[c]", a stack holds the string built so far and the repeat count waiting for a ']'. Digits accumulate a count, '[' pushes a checkpoint, letters append to the current fragment, ']' pops and expands.

What to focus on

Innermost ] resolves first (LIFO). After expand, the piece is appended to the previous fragment (the new top).

Worked examples

one group

s = "3[ab]"
  1. count 3
  2. frag ab
  3. ] → ababab

Result: "ababab"

nested

s = "2[a3[b]]"
  1. inner bbb
  2. outer a + bbb twice

Result: "abbbabbb"

plain

s = "ab"
  1. no brackets
  2. append

Result: "ab"

Try it

Write decode(s). s is a well-formed decode string. Return the expanded string. The ] that closes the inner group runs first. s = \"3[ab]\" → \"ababab\". s = \"2[a3[b]]\" → \"abbbabbb\". s = \"ab\" → \"ab\".

s is a well-formed decode string: matching brackets, counts are positive integers, letters are lowercase. No leftover '['.

practise it with Awel find your weak spots: free skill check