· By John Kavanagh

Decode String in TypeScript: Save the Context Before the Bracket

Nested brick archways frame a doorway in Samarkand.
Image by Marco D'Abramo, licensed from Unsplash.

The difficult part of a repeated string isn't repetition. JavaScript already has a method for that. The difficult part is remembering what we were building before a nested expression interrupted it.

In LeetCode's Decode String problem, a positive integer before square brackets tells us how many times to repeat their contents. Those contents can themselves contain repetitions. I'll keep one frame per open bracket, holding the prefix we have already decoded and the repeat count waiting to be applied.

That frame is the information a recursive parser would otherwise leave on its call stack. Making it explicit lets us trace nesting without relying on recursive calls. It also makes the state reset at an opening bracket quite hard to miss, which is fortunate because that is an easy place to introduce a very persistent number.


There are Four Kinds of Input Character

A digit extends the repeat count. An opening bracket saves the surrounding context and begins a new inner string. A closing bracket finishes that inner string and combines it with the saved prefix. A letter extends the current string.

The digit case must accumulate a decimal number: multiply the previous count by ten, then add the new digit. For 12[a], reading one and then two must produce twelve, not two, and certainly not three. The problem guarantees that digits describe counts rather than literal output characters.

At an opening bracket, the current prefix and count belong together. I store them in one typed object rather than two parallel stacks. Separate stacks can work, but they introduce a synchronisation rule we can avoid by representing a frame as one value.

After pushing the frame, reset both the current string and count. The inner expression starts fresh. On closing, pop the matching frame, repeat the completed inner string, and append that expansion to the saved prefix. The result becomes the current string in the enclosing context.

type DecodeFrame = { prefix: string; count: number };

const decodeString = (source: string): string => {
  const frames: DecodeFrame[] = [];
  let current = '';
  let count = 0;
  for (const character of source) {
    if (character >= '0' && character <= '9') {
      count = count * 10 + Number(character);
    } else if (character === '[') {
      frames.push({ prefix: current, count });
      current = '';
      count = 0;
    } else if (character === ']') {
      const frame = frames.pop();
      if (!frame) throw new Error('Unexpected closing bracket');
      current = frame.prefix + current.repeat(frame.count);
    } else {
      current += character;
    }
  }
  return current;
};

This code assumes the valid grammar supplied by the problem. The guard on an unexpected closing bracket makes that particular failure explicit, but it is not a complete input validator. Unclosed brackets, a count without a following bracket, or unsupported characters would need their own validation rules in a general parser.

The comparison against the characters zero and nine is sufficient because the input's digits are the ordinary decimal characters. I wouldn't advertise it as a Unicode numeric parser. Narrow input assumptions are useful when they are visible rather than accidentally buried in a conversion function.


Unwinding a Nested Example

Consider x2[a3[b]]y. Reading x gives us the prefix x. Reading two sets the count to two. At the opening bracket, we save { prefix: 'x', count: 2 }, then begin an empty inner string.

Reading a makes the current string a. Reading three and the next opening bracket saves a second frame containing that prefix and count. The frame stack now records both unfinished repetitions, with the inner one on top.

The letter b becomes the innermost current string. Its closing bracket restores the inner frame and combines a with three copies of b, producing abbb. The next closing bracket restores the outer frame and combines x with two copies of abbb, producing xabbbabbb.

Finally, y is appended, giving xabbbabbby. The outer prefix was preserved exactly once, and the inner count never leaked into the outer repetition. Writing out those intermediate strings is a more useful debugging exercise than staring at the final output and trying to count the bees.

Adjacent expressions work without any extra rule. After decoding 2[ab], the current string contains abab. Opening 3[c] saves that string as its prefix, then appends the completed repetition when the bracket closes. The same frame mechanism handles both nesting and adjacency.


What Each Frame Guarantees

At any point in the scan, current contains the decoded material already completed inside the innermost open bracket, or at the top level when no bracket is open. Each saved frame holds the completed prefix and repetition count of one suspended enclosing level.

Opening a bracket preserves that information before resetting the working variables. Closing a bracket combines exactly one completed inner result with exactly one saved outer context. Because brackets are properly nested, the most recently saved frame is always the one we need next.

This explains why a queue would be wrong. Restoring the earliest saved frame first would combine an inner expansion with the outermost prefix before its immediate parent had been completed. The nesting order requires last in, first out.

It also explains why a global replacement of the first bracketed substring is a less attractive implementation. You can repeatedly find innermost expressions and replace them, but then you keep rescanning and rebuilding the encoded text. The stack follows the grammar directly and consumes each input character once.


Count the Output Work Honestly

Scanning n input characters takes O(n) parser steps. Producing an expanded result of length L necessarily takes at least O(L) work when the final characters are materialised. A short input can describe a much longer output, so O(n) alone is not a complete runtime claim.

There is a further qualification for this straightforward string‑building implementation. JavaScript engines can represent concatenated strings differently, and repeated prefix concatenation or nested expansion may copy intermediate text. I would not claim a universal O(n + L) copying bound for this code merely because its parser loop is linear.

Under a conservative model that copies complete strings on each concatenation, there can be up to n constructions, each involving at most L output characters, giving an O(nL + n) upper bound. The exercise limits both encoded and expanded lengths, making the simple implementation reasonable without an elaborate output tree.

Live logical string contents across the current result and saved prefixes occupy O(L) characters, with O(d) frames for nesting depth d, excluding the source and temporary allocations during concatenation. Engine allocation behaviour can differ from that abstract accounting. For much larger inputs, I would consider a parsed repetition tree and a controlled output pass rather than repeatedly materialising nested strings.


A Production Parser Needs an Expansion Policy

The exercise guarantees a bounded decoded length. A service accepting arbitrary encoded input cannot rely on that promise. Counts and nesting can describe more output than memory allows, even when the input is small and syntactically valid.

A robust version would validate the grammar, limit nesting and counts, and check the projected output length before expanding. If output must be streamed, it also needs to define what happens when a limit is reached after some characters have already been emitted. Those are interface decisions, not something a try‑catch around repeat settles.

For this article, the complete inline implementation remains deliberately tied to the exercise's valid inputs. Keeping that scope explicit is preferable to adding a few isolated guards and calling the result safe for arbitrary data.


Verify the Nesting Independently

I compare the iterative decoder with a small recursive reference parser on generated valid expressions. The reference consumes one grammatical sequence at a time, so it reaches the answer through a different control structure. Useful fixed cases include plain letters, adjacent repetitions, multi‑digit counts, several nesting levels, and text before and after a repetition.

My Simplify Path article uses a stack for cancellation rather than suspended contexts, and my circular queue walkthrough makes the difference in removal order explicit. Here the thing to retain is the frame: save everything the enclosing expression will need, then let the inner expression finish. The closing bracket is a return point with punctuation.


Have a complex web platform issue?

Tell me what is blocked, what has changed, and what needs to be true after the fix. I'll come back with a practical next step.