The challenge
Decode nested k[encoded] groups, preserving literal letters.
ASCII letters, positive integer repeat counts, balanced brackets. Decoded length L ≤ 100,000.
Example
3[a2[c]] → accaccacc.
Use the walkthrough below to inspect the input and each state change.
See Decode a Repeated String, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 10
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: ["3","[","a","2","[","c","]","]"]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Save (prefix, count) on [, then restore and expand on ].
Indices are zero-based. C++ uses C++17 or later.
def solve(values):
stack = []
text, count = '', 0
for c in values:
if c.isdigit(): count = 10 * count + int(c)
elif c == '[':
stack.append((text, count))
text, count = '', 0
elif c == ']':
prefix, repeat = stack.pop()
text = prefix + text * repeat
else: text += c
return text
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
string solve(const vector<string>& values) {
vector<pair<string, int>> stack;
string text;
int count = 0;
for (const auto& token : values) {
char c = token[0];
if (c >= '0' && c <= '9') count = 10 * count + c - '0';
else if (c == '[') {
stack.push_back({text, count});
text.clear(); count = 0;
} else if (c == ']') {
auto [prefix, repeat] = stack.back(); stack.pop_back();
string expanded = prefix;
for (int i = 0; i < repeat; ++i) expanded += text;
text = expanded;
} else text += c;
}
return text;
}