Problem overview
The method decodeString receives an encoded string s and returns the decoded one. The encoding rule is k[encoded_string]: the text inside the brackets is repeated exactly k times. The input is always valid, and digits appear only as repeat counts, so there is never a 3a or a 2[4]. Counts can have several digits, up to 300, and brackets can be nested.
For "3[a]2[bc]" the result is "aaabcbc": a three times, then bc twice. For "3[a2[c]]" the inner 2[c] becomes cc, so the outer block repeats acc three times and the result is "accaccacc". In "2[abc]3[cd]ef", the trailing ef has no brackets and is copied as it is, giving "abcabccdcdcdef".
Approach: one buffer per open bracket
Nesting is the whole difficulty. When the scan reaches the inner [ in 3[a2[c]], the outer block is still unfinished: it holds a so far and waits for the inner block to be decoded and appended. Only when the matching ] arrives can the inner block be repeated and merged into the one around it.
That "last opened, first closed" order is exactly what a stack provides. This solution keeps a stack of strings with two kinds of entries:
- a number entry is a repeat count, stored as a string of digits;
- a text entry is the decoded text of one open bracket level.
A [ opens a new, empty text entry. A letter is appended to the top text entry. A digit either starts a new number entry or extends the number on top, which handles counts like 23. A ] pops the finished text and the count below it, repeats the text, and appends the result to whatever is now on top.
The invariant to keep in mind is that a count always sits directly below the text entry it applies to. Counts are pushed when digits are read, and the [ that follows pushes the text entry on top of them.
Step by step
- Create the empty
stack. It is aconstbecause the array itself is never replaced, only changed withpushandpop. - Loop over the characters with
for (const c of s). Iterating a string withfor...ofgives one character at a time. - Handle
[. Push an empty string, the buffer for the new level. - Handle letters. If the stack is empty, which happens for letters before any bracket such as the
efat the end of the third example, push an empty buffer first. Then append the letter to the top entry. - Handle digits. Read the top entry, or an empty string if the stack is empty. If the top is not made only of digits, the digit starts a new count, so push it as its own entry. Otherwise the previous character was also a digit, so append this one to the number on top.
- Handle
]. This is the finalelse, since valid input has nothing else left. Pop the text entry, pop the count below it and convert it to a number, and build the repeated text. - Fold the result back in. If the stack is now empty, the decoded piece is top level, so push it. Otherwise append it to the text entry one level up.
- Return the top entry. For valid input exactly one entry remains: the whole decoded string.
Here is "3[a2[c]]" traced. The stack after each character is shown with the top on the right:
3 -> ["3"]
[ -> ["3", ""]
a -> ["3", "a"]
2 -> ["3", "a", "2"]
[ -> ["3", "a", "2", ""]
c -> ["3", "a", "2", "c"]
] -> ["3", "acc"]
] -> ["accaccacc"]
The solution in JavaScript
class Solution {
decodeString(s) {
const stack = [];
for (const c of s) {
if (c === '[') {
stack.push("");
} else if (/[a-zA-Z]/.test(c)) {
if (stack.length === 0) {
stack.push("");
}
stack[stack.length - 1] += c;
} else if (/[0-9]/.test(c)) {
const top = stack.length > 0 ? stack[stack.length - 1] : "";
if (!/^\d+$/.test(top)) {
stack.push(c);
} else {
stack[stack.length - 1] += c;
}
} else {
const currStr = stack.pop();
const currNum = parseInt(stack.pop());
const repeated = currStr.repeat(currNum);
if (stack.length === 0) {
stack.push(repeated);
} else {
stack[stack.length - 1] += repeated;
}
}
}
return stack[stack.length - 1];
}
}
JavaScript details worth knowing:
- Strings are immutable.
stack[stack.length - 1] += cdoes not edit a string in place. It builds a new string and stores it back in the slot. That is fine here. /regex/.test(c)returns a boolean./[a-zA-Z]/matches one letter, and/^\d+$/matches a string made only of one or more digits. The+means an empty string fails, so an empty buffer is never mistaken for a number.parseIntconverts the digit string, for example"12"to12. Called with one argument it parses base 10 for digit strings like these."ab".repeat(3)returns"ababab". A count of 0 would give an empty string, though the problem guarantees counts of at least 1.pop()on an empty array returnsundefinedinstead of throwing. Valid input never causes that here, but it is why a malformed input would fail later with a confusing error rather than at the pop.stack[stack.length - 1]is how JavaScript reads the top of an array. Negative indexes likestack[-1]do not work and giveundefined.
Complexity
Let L be the length of the decoded output, which the problem bounds by 100,000.
Time: each input character is handled once, in constant work apart from string building. Building strings costs time proportional to their length, and nested repeats copy text more than once: a piece of text is copied again each time an enclosing level folds it into its parent. With at most 30 input characters, nesting is shallow, so the total work stays close to O(L) in practice. For very deep nesting the copying could cost more, so treat O(L) as the typical figure, not a strict bound.
Space: the stack holds the partly decoded text of each open level, so it is O(L) at worst, plus the final string.
Edge cases and common mistakes
- Multi-digit counts.
"12[x]"must give twelvexcharacters. Pushing every digit as a separate entry would leave the stack in the wrong shape; the solution extends the number on top instead. - Letters before any bracket.
"ab2[c]"decodes to"abcc". The lazy empty buffer in the letter branch makes this work. - Text after a block. After
], the next letters append to the entry on top, so"2[a]b"gives"aab". - Nesting several levels deep.
"2[a2[b2[c]]]"gives"abccbccabccbcc". Each]only merges one level. - Popping in the wrong order. The text is on top and the count is below it. Popping the count first would try to repeat a number.
- Forgetting to convert the count.
repeatdoes convert a numeric string on its own, but converting explicitly withparseIntkeeps the intent clear.
Testing
"3[a]2[bc]"gives"aaabcbc"."3[a2[c]]"gives"accaccacc"."2[abc]3[cd]ef"gives"abcabccdcdcdef"."ab2[c]"gives"abcc"."12[x]"gives"xxxxxxxxxxxx".