medium

Decode String

Expand nested k[text] patterns using two stacks that park the repeat count and the text built before each bracket.

1. Define the problem

Decode String

You are given an encoded string and must expand it. The pattern ktext means "repeat text exactly k times". These patterns can sit inside each other. "2[a3b]" means the block "a3b" repeated twice, and inside it "b" is repeated three times, so the answer is "abbbabbb". Because an inner pattern must finish before the outer one can, this is a job for two stacks : one holding the repeat counts you have not used yet, and one holding the text you had built up before each opening bracket. When you meet a closing bracket, you pop both stacks and glue the saved text in front of the finished inner text repeated that many times.

Constraints

  • 1 ≤ s.length ≤ 30
  • s contains lowercase letters, digits and square brackets
  • s is always a valid encoding, so brackets are balanced
  • 1 ≤ k ≤ 300
  • The decoded string is at most 105 characters long

Example

Inputs = "2[a3b]"
Output"abbbabbb"

Explanation The inner 3[b] becomes "bbb", which makes the inner block "abbb". Repeating that block twice gives "abbbabbb".

2. Know the words first

In plain terms

Encoded
Written in a shorter form using a rule. Here the rule is that a number in front of brackets means repeat what is inside.
Nested
One pattern sitting completely inside another, like brackets inside brackets.
Stack
A pile where you add and remove only at the top, which matches how the innermost bracket always finishes first.
Repeat count
The number written just before an opening bracket. It says how many copies of the inner text to make.
3. Visualize the solution

The row is the saved-work stack: each cell holds one repeat count and the text saved with it

The row is the saved-work stack: each cell holds one repeat count and the text saved with it
Statusinit

Start with empty stacks. current is the text built so far, and it is empty.

What happens in this step

s = "2[a3[b]]"
countStack = [], textStack = []
count = 0
current = ""

Nothing has been read yet, so every slot shows a dash.
Step 1 of 7

Steps to visualize

  1. Each filled cell reads count|"text": the number in front of an opening bracket, and whatever text had been built before it.
  2. A dash means an empty slot. The value called current is the text being built right now, shown in the step detail.
  3. An opening bracket pushes a new cell and clears current, because a fresh inner block is starting.
  4. A closing bracket pops the top cell and sets current to saved text plus current repeated count times.
  5. When the string ends, the stack is empty and current holds the decoded answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the saved-work stack: each cell holds one repeat count and the text saved with it
Statusinit

Start with empty stacks. current is the text built so far, and it is empty.

What happens in this step

s = "2[a3[b]]"
countStack = [], textStack = []
count = 0
current = ""

Nothing has been read yet, so every slot shows a dash.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function decodeString(s) {
  const countStack = [];
  const textStack = [];
  let count = 0;
  let current = '';

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      count = count * 10 + Number(ch);
    } else if (ch === '[') {
      countStack.push(count);
      textStack.push(current);
      count = 0;
      current = '';
    } else if (ch === ']') {
      const repeat = countStack.pop();
      current = textStack.pop() + current.repeat(repeat);
    } else {
      current += ch;
    }
  }

  return current;
}
Time
O(n) in the length of the decoded string
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
s = "2[a3b]""abbbabbb"example from the description, with one pattern inside another
s = "3[a]2[bc]""aaabcbc"two separate patterns one after the other
s = "abc""abc"plain text with nothing to expand
s = "2[abc]3[cd]ef""abcabccdcdcdef"loose letters after the repeated blocks
s = "10[a]""aaaaaaaaaa"a repeat count with more than one digit
s = "3[a2c]""accaccacc"nesting with letters before the inner block

Keep reading