Decode String
Decode String is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (two stacks), runs in O(n + d · m) time and O(n + m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (expand innermost brackets) up.
Problem
A string is encoded with the rule k[text], which stands for text written exactly k times in a row. Blocks can be nested, and plain letters can appear anywhere outside or inside blocks.
Given a valid encoded string s, return its decoded form.
Examples
Example 1
- Input
s = "2[ab]c"- Output
"ababc"- Why
- ab is written twice, then c follows once.
Example 2
- Input
s = "x3[y2[z]]"- Output
"xyzzyzzyzz"- Why
- The inner 2[z] becomes zz, so 3[yzz] becomes yzzyzzyzz, after the leading x.
Example 3
- Input
s = "10[q]1[rs]"- Output
"qqqqqqqqqqrs"- Why
- Counts can have more than one digit, and a count of 1 just copies the block.
Constraints
1 <= s.length <= 3000scontains lowercase letters, digits and square brackets, and is always well formed.- Digits only appear as repeat counts, each count is between 1 and 300, and it is always followed by
[. - The decoded string has at most
10^5characters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (expand innermost brackets) | O(B · m) | O(m) |
| Optimal (two stacks) | O(n + d · m) | O(n + m) |
1Brute force (expand innermost brackets)
O(B · m)Each of the B blocks rebuilds a string of length up to m, the decoded length.O(m)The rebuilt string.The first ] and the closest [ before it always form an innermost block with no brackets inside. Expand that block in place and repeat until no brackets remain.
- Find close = first index of ']'; stop if there is none.
- Find open = last index of '[' before close, and walk left over the digits before it to get k.
- Replace k[body] with body repeated k times.
- Repeat.
class Solution {
public String decodeString(String s) {
while (true) {
int close = s.indexOf(']');
if (close < 0) return s;
int open = s.lastIndexOf('[', close);
int d = open;
while (d > 0 && Character.isDigit(s.charAt(d - 1))) d--;
int k = Integer.parseInt(s.substring(d, open));
String body = s.substring(open + 1, close);
s = s.substring(0, d) + body.repeat(k) + s.substring(close + 1);
}
}
}class Solution:
def decodeString(self, s: str) -> str:
while True:
close = s.find(']')
if close < 0:
return s
open_ = s.rfind('[', 0, close)
d = open_
while d > 0 and s[d - 1].isdigit():
d -= 1
k = int(s[d:open_])
body = s[open_ + 1:close]
s = s[:d] + body * k + s[close + 1:]class Solution {
public:
string decodeString(string s) {
while (true) {
size_t close = s.find(']');
if (close == string::npos) return s;
size_t open = s.rfind('[', close);
size_t d = open;
while (d > 0 && isdigit((unsigned char)s[d - 1])) d--;
int k = stoi(s.substr(d, open - d));
string body = s.substr(open + 1, close - open - 1);
string rep;
rep.reserve(body.size() * k);
for (int i = 0; i < k; i++) rep += body;
s = s.substr(0, d) + rep + s.substr(close + 1);
}
}
};function decodeString(s) {
while (true) {
const close = s.indexOf(']');
if (close < 0) return s;
const open = s.lastIndexOf('[', close);
let d = open;
while (d > 0 && s[d - 1] >= '0' && s[d - 1] <= '9') d--;
const k = parseInt(s.slice(d, open), 10);
const body = s.slice(open + 1, close);
s = s.slice(0, d) + body.repeat(k) + s.slice(close + 1);
}
}2Optimal (two stacks)
O(n + d · m)Each input character is read once; an output character is copied once for each closing bracket around it, so at most d times (d = nesting depth).O(n + m)The stacks hold at most one saved text per open bracket, plus the output.Scan once, keeping the text of the current bracket level and the number being read. On [ push the count and the current text and start a new level; on ] pop them and append the current text repeated count times to the saved text.
- cur = empty, k = 0; counts and texts are empty stacks.
- Digit: k = k · 10 + digit.
- '[': push k and cur; reset cur = empty, k = 0.
- ']': rep = popped count, prev = popped text; cur = prev + cur repeated rep times.
- Letter: append it to cur. Return cur at the end.
class Solution {
public String decodeString(String s) {
Deque<Integer> counts = new ArrayDeque<>();
Deque<StringBuilder> texts = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
int k = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
k = k * 10 + (c - '0');
} else if (c == '[') {
counts.push(k);
texts.push(cur);
cur = new StringBuilder();
k = 0;
} else if (c == ']') {
int rep = counts.pop();
StringBuilder prev = texts.pop();
for (int i = 0; i < rep; i++) prev.append(cur);
cur = prev;
} else {
cur.append(c);
}
}
return cur.toString();
}
}class Solution:
def decodeString(self, s: str) -> str:
counts, texts = [], []
cur, k = [], 0
for c in s:
if c.isdigit():
k = k * 10 + int(c)
elif c == '[':
counts.append(k)
texts.append(cur)
cur, k = [], 0
elif c == ']':
rep = counts.pop()
prev = texts.pop()
prev.append(''.join(cur) * rep)
cur = prev
else:
cur.append(c)
return ''.join(cur)class Solution {
public:
string decodeString(string s) {
vector<int> counts;
vector<string> texts;
string cur;
int k = 0;
for (char c : s) {
if (isdigit((unsigned char)c)) {
k = k * 10 + (c - '0');
} else if (c == '[') {
counts.push_back(k);
texts.push_back(cur);
cur.clear();
k = 0;
} else if (c == ']') {
int rep = counts.back();
counts.pop_back();
string prev = move(texts.back());
texts.pop_back();
for (int i = 0; i < rep; i++) prev += cur;
cur = move(prev);
} else {
cur += c;
}
}
return cur;
}
};function decodeString(s) {
const counts = [], texts = [];
let cur = '', k = 0;
for (const c of s) {
if (c >= '0' && c <= '9') {
k = k * 10 + (c.charCodeAt(0) - 48);
} else if (c === '[') {
counts.push(k);
texts.push(cur);
cur = '';
k = 0;
} else if (c === ']') {
const rep = counts.pop();
cur = texts.pop() + cur.repeat(rep);
} else {
cur += c;
}
}
return cur;
}Edge cases to test
- No brackets at all (the string is returned unchanged)
- Multi-digit counts like 12[a]
- Deep nesting such as 2[2[2[a]]]
- Letters before, between and after encoded blocks
Hints
Hint 1
Each k[ opens a new context that must be finished before you can continue the outer one. Which data structure handles that?
Hint 2
When you see [, save the text built so far and the count, then start fresh.
Hint 3
When you see ], repeat the current text k times and append it to the saved text.
FAQ
What is the best time complexity for Decode String?
Optimal (two stacks) runs in O(n + d · m) time and O(n + m) extra space. Each input character is read once; an output character is copied once for each closing bracket around it, so at most d times (d = nesting depth).
Which pattern does Decode String use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Decode String?
Yes. Brute force (expand innermost brackets) takes O(B · m) time and O(m) space. The first ] and the closest [ before it always form an innermost block with no brackets inside.
Which edge cases should I test for Decode String?
No brackets at all (the string is returned unchanged); Multi-digit counts like 12[a]; Deep nesting such as 2[2[2[a]]]; Letters before, between and after encoded blocks.