Decode String

Medium

Problem

Decode a string encoded as k[encoded], meaning the part inside the brackets repeated k times. Brackets can be nested, and the input is always valid.

Example 1

Input:  "3[a]2[bc]"
Output: "aaabcbc"

Example 2

Input:  "3[a2[c]]"
Output: "accaccacc"

Test cases

Case 1

Input:    "3[a]2[bc]"
Expected: "aaabcbc"

Case 2

Input:    "3[a2[c]]"
Expected: "accaccacc"

Case 3

Input:    "2[abc]3[cd]ef"
Expected: "abcabccdcdcdef"

Case 4

Input:    "10[a]"
Expected: "aaaaaaaaaa"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Stack of (previous string, repeat count)

Time O(output length)Space O(output length)

On "[" save the current string and number and start fresh; on "]" pop and append the current string repeated.

function decodeString(s) {
const st = [];
let cur = '', num = 0;
for (const c of s) {
if (c >= '0' && c <= '9') num = num * 10 + Number(c);
else if (c === '[') { st.push([cur, num]); cur = ''; num = 0; }
else if (c === ']') { const [prev, k] = st.pop(); cur = prev + cur.repeat(k); }
else cur += c;
}
return cur;
}