Decode a Run-Length Nested Encoded String
Solve this Problems in the form k[encoded_string] (where k is a positive integer, possibly nested arbitrarily deep), decode it by repeating each bracketed substring k times.
Recursively parsing this works, but finding each bracket's match by scanning forward wastes effort re-treading the string. A single-pass approach with two stacks avoids that entirely: track the string being built at the current nesting level, and whenever a new level opens ('['), push the pending repeat count and the string built so far, then start fresh. Whenever a level closes (']'), pop both back off and fold the finished level in — repeat it and prepend what came before. The stack always knows exactly where to resume, with no need to ever locate a matching bracket's position in advance.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 15 - ◆
s is a valid encoding: k[encoded_string], where k is a positive integer and encoded_string only contains lowercase letters, digits, and further valid k[...] patterns - ◆
The decoded output length never exceeds 100 characters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Parse With a Bracket-Matching Scan
BruteParse the string recursively over a range [start, end). At each position: a run of digits is a repeat count; the '[' that follows it needs its matching ']' found by scanning forward and tracking bracket depth (incrementing on '[', decrementing on ']', stopping when depth returns to 0); the substring between them is decoded recursively and repeated that many times. A plain letter is just copied. This is correct, but re-scanning forward to find each matching bracket costs O(distance to that bracket), and that distance can be O(n) — with up to n brackets to match across all the recursive calls, that's O(n²) total scanning work.
O(n²)O(n)1class Solution {
2 public String decodeString(String s) {
3 return decode(s, 0, s.length());
4 }
5
6 private String decode(String s, int start, int end) {
7 StringBuilder result = new StringBuilder();
8 int i = start;
9 while (i < end) {
10 if (Character.isDigit(s.charAt(i))) {
11 int num = 0;
12 while (Character.isDigit(s.charAt(i))) {
13 num = num * 10 + (s.charAt(i) - '0');
14 i++;
15 }
16 int openIdx = i;
17 int depth = 0;
18 int closeIdx = -1;
19 for (int k = openIdx; k < end; k++) {
20 if (s.charAt(k) == '[') depth++;
21 else if (s.charAt(k) == ']') {
22 depth--;
23 if (depth == 0) { closeIdx = k; break; }
24 }
25 }
26 String inner = decode(s, openIdx + 1, closeIdx);
27 for (int r = 0; r < num; r++) result.append(inner);
28 i = closeIdx + 1;
29 } else {
30 result.append(s.charAt(i));
31 i++;
32 }
33 }
34 return result.toString();
35 }
36}Optimal — Single Pass With Two Stacks
OptimalWalk the string once, maintaining the string built so far for the current bracket depth (cur) plus two stacks: one for pending repeat counts, one for the string-so-far at each enclosing level. Digits accumulate into a pending count. On '[', push the current count and the current partial string, then reset both — a fresh level starts. On ']', pop the count and the enclosing string, and fold the just-finished level in: repeat cur that many times and prepend the enclosing string. No bracket-matching scan is ever needed — the stack itself remembers exactly where to resume.
O(n · maxRepeat)O(n)1class Solution {
2 public String decodeString(String s) {
3 Deque<Integer> countStack = new ArrayDeque<>();
4 Deque<String> strStack = new ArrayDeque<>();
5 String cur = "";
6 int num = 0;
7 for (char c : s.toCharArray()) {
8 if (Character.isDigit(c)) {
9 num = num * 10 + (c - '0');
10 } else if (c == '[') {
11 countStack.push(num);
12 strStack.push(cur);
13 num = 0;
14 cur = "";
15 } else if (c == ']') {
16 int k = countStack.pop();
17 String prev = strStack.pop();
18 StringBuilder repeated = new StringBuilder();
19 for (int r = 0; r < k; r++) repeated.append(cur);
20 cur = prev + repeated.toString();
21 } else {
22 cur += c;
23 }
24 }
25 return cur;
26 }
27}