Faangprep Logo
Log inStart free
Browse curriculum

Decode String

Decode an encoded string with nested repetition rules.

MediumSolve on LeetCode

Problem Understanding

You are given an encoded string where k[encoded_string] means the encoded_string inside the brackets is repeated exactly k times. You may assume the input string is always valid.

Example:

  • Input: 3[a]2[bc] -> Output: aaabcbc
  • Input: 3[a2[c]] -> Output: accaccacc (Nested!)

Algorithm Strategy

We use a Stack to handle the nested nature of the problem.

  1. Initialize an empty stack.
  2. Iterate through the string character by character.
  3. If the char is NOT ], push it to the stack.
  4. If the char IS ], we must start decoding:
    • Pop characters until we find [. This is the string_to_repeat.
    • Pop the [.
    • Pop numbers to form k (the repetition count).
    • Repeat string_to_repeat k times and Push it back to the stack.
  5. Finally, join the stack to get the result.

Interactive Visualization

Visualize how the stack builds nested strings from the inside out.

Dry Run

Input: 3[a2[c]]

Char Action Stack
3,[,a,2,[,c Push all ['3', '[', 'a', '2', '[', 'c']
] Pop until [. K=2. Repeat c x2. ['3', '[', 'a', 'cc']
] Pop until [. String=acc. K=3. Repeat acc x3. ['accaccacc']

Result: accaccacc

Edge Cases & Common Mistakes

  • Multi-digit K: e.g., 10[a]. Ensure you parse the full number.
  • Empty Brackets: 3[] -> Empty string.
  • No Brackets: abc -> abc.

Solution

Stack Implementation.

Decode String Code
1var decodeString = function(s) {
2    const stack = [];
3    for (const ch of s) {
4        if (ch !== ']') {
5            stack.push(ch);
6        } else {
7            let chunk = '';
8            while (stack[stack.length - 1] !== '[') {
9                chunk = stack.pop() + chunk;
10            }
11            stack.pop(); // drop "["
12            let k = '';
13            while (stack.length > 0 && /^\d$/.test(stack[stack.length - 1])) {
14                k = stack.pop() + k;
15            }
16            stack.push(chunk.repeat(Number(k)));
17        }
18    }
19    return stack.join('');
20};
Previous

Valid Parentheses

Next

Longest Valid Parentheses

The approach, step by step

  1. Push until "]"

    Push every character that is not a closing bracket.

  2. Collect the group

    On "]", pop chunks into the group text until "[", drop it, and pop the digits below into k.

  3. Push it back

    Push the group text repeated k times, and join the stack at the end.

Frequently asked questions

How does a stack decode nested strings like 3[a2[c]]?

Push characters until a "]". Then pop chunks back to the "[", drop it, pop the digits for k, and push the chunk repeated k times. Inner groups close first, so their decoded text is already one chunk when the outer group repeats it.

How are multi-digit counts like 10[x] handled?

The digits are pushed one at a time, so after dropping "[" the code keeps popping while the top is a digit and prepends each one, giving "10".

What is the complexity of Decode String?

Proportional to the input length n plus the decoded length L for the pushes and pops; building each chunk by prepending can add up to O(n · L) character copies.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description