AlgoMaster Logo

Decode String

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We have a string where patterns like k[...] mean "repeat whatever is inside the brackets k times." These patterns can be nested. 3[a2[c]] means: first decode the inner 2[c] to get "cc", combine it with the "a" before it to get "acc", and then repeat that whole thing 3 times to get "accaccacc".

The brackets nest the way parentheses nest in mathematical expressions. When we see an opening bracket, we have to set aside what we were building and the multiplier that applies to it, decode the inside, and then come back and apply the multiplier. That save-and-restore pattern is what a stack or recursion provides.

Innermost brackets resolve first, and their result feeds into the outer brackets. A stack matches this inside-out order because the most recently opened bracket is always the first one to close.

Key Constraints:

  • 1 <= s.length <= 30 → The input is tiny, but the output can be up to 10^5 characters, so the cost is dominated by building the decoded string, not scanning the input.
  • Integers are in range [1, 300] → Repeat counts can be up to 3 digits, so number parsing has to accumulate digits (num = num * 10 + digit) rather than read a single character.
  • s is guaranteed to be valid → No need to handle malformed inputs. Every [ has a matching ], and every [ is preceded by a number.

Approach 1: Brute Force (Repeated String Replacement)

Intuition

Find the innermost bracket pair (one that contains no other brackets inside it), decode it by repeating its content, splice the result back into the string, and repeat until no brackets remain.

The innermost pair is safe to decode first because its content is plain text with no nested structure. Each substitution removes one bracket pair, so after one pass per pair the string contains no brackets and is fully decoded.

Algorithm

  1. Scan the string for the innermost bracket pair: find a ] and then look backwards for its matching [.
  2. Extract the number before the [ and the string between [ and ].
  3. Replace the entire number[string] with the repeated string.
  4. Repeat until no brackets remain in the string.

Example Walkthrough

1Find innermost brackets: first ']' at index 6, matching '[' at index 4
0
3
1
[
2
a
3
2
k=2
4
[
5
c
6
]
innermost
7
]
1/5

Code

Rebuilding the entire string on every pass is wasted work. The next approach decodes everything in a single left-to-right scan.

Approach 2: Stack-Based (Optimal)

Intuition

Instead of repeatedly scanning and replacing, we can process the string in one left-to-right pass using a stack. As we walk through the string, we build the current decoded string character by character. When we hit a [, we save the current string and the pending repeat count by pushing them onto the stack, and start fresh for the inner content. When we hit a ], we pop the saved state, repeat the current string the required number of times, and append it to the saved string.

Algorithm

  1. Initialize an empty stack, currentString as empty, and currentNum as 0.
  2. Iterate through each character in the string:
    • If it's a digit, build the number: currentNum = currentNum * 10 + digit (handles multi-digit numbers like 12 or 300).
    • If it's [, push (currentString, currentNum) onto the stack, then reset currentString to empty and currentNum to 0.
    • If it's ], pop (previousString, repeatCount) from the stack. Set currentString = previousString + currentString repeated repeatCount times.
    • If it's a letter, append it to currentString.
  3. Return currentString.

Example Walkthrough

s
1Start: scan character by character. currentString="", currentNum=0
0
3
i
1
[
2
a
3
2
4
[
5
c
6
]
7
]
stack
1Stack empty
1/8

Code

Recursion expresses the same idea without an explicit stack: each recursive call holds the saved state in its own stack frame.

Approach 3: Recursive

Intuition

The structure of this problem is inherently recursive. A valid encoded string is either a sequence of regular characters (base case) or a number followed by [encoded_string] where encoded_string is itself a valid encoded string (recursive case).

So we can write a function that processes characters one by one. When it sees a digit, it reads the full number, skips the [, recursively decodes the content up to the matching ], and repeats the result. When it sees a letter, it appends it. A shared index variable, advanced by every call, tells the caller where the recursive call stopped reading.

Algorithm

  1. Maintain a pointer index that tracks our position in the string.
  2. Define a recursive function decode():
    • Initialize a result string.
    • While index is within bounds and the current character is not ]:
      • If it's a digit, parse the full number, skip the [, recursively decode until ], skip the ], and append the repeated decoded string to result.
      • If it's a letter, append it to result and advance index.
    • Return the result string.
  3. Call decode() starting at index 0.

Example Walkthrough

1Call decode(). index=0: '2' is digit → num=2
0
2
index
1
[
2
a
3
b
4
c
5
]
6
3
7
[
8
c
9
d
10
]
11
e
12
f
1/7

Code