Decode String

Problem Description

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

Examples

Constraints

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[' and ']'.
• s is guaranteed to be a valid input.
• All the integers in s are in the range [1, 300].

Stacks for Counts and Substrings

Since brackets can be nested (e.g. 3[a2[c]]), we must resolve inner brackets before outer ones. This matches a stack-based structure. We can use two stacks: countStack to store repetition factors k, and stringStack to store the text prefix built before entering the brackets. We iterate through the string character by character:

• If we see a digit, we parse the full number (which can be multiple digits, like 300) and update our current multiplier.
• If we see [, we push the current multiplier onto countStack and the current string builder state onto stringStack, then reset both.
• If we see ], we pop the count from countStack, repeat the current string builder that many times, and prepend the popped prefix from stringStack.
• Otherwise, append the character to our current string builder.

Solution 1: Count and String Double Stacks

Use two stacks to resolve nested repetition coefficients and string states.

import java.util.Stack;

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0'); // parse multi-digit integers
            } else if (c == '[') {
                countStack.push(k);
                stringStack.push(currentString);
                currentString = new StringBuilder(); // reset current string
                k = 0; // reset multiplier
            } else if (c == ']') {
                StringBuilder decodedString = stringStack.pop();
                int count = countStack.pop();
                for (int j = 0; j < count; j++) {
                    decodedString.append(currentString);
                }
                currentString = decodedString; // update active string
            } else {
                currentString.append(c);
            }
        }
        return currentString.toString();
    }
}

class Solution:
    def decodeString(self, s: str) -> str:
        count_stack = []
        string_stack = []
        current_string = []
        k = 0
        
        for char in s:
            if char.isdigit():
                k = k * 10 + int(char)  # parse multi-digit integers
            elif char == '[':
                count_stack.append(k)
                string_stack.append(current_string)
                current_string = []  # reset current string
                k = 0  # reset multiplier
            elif char == ']':
                count = count_stack.pop()
                prev_string = string_stack.pop()
                current_string = prev_string + current_string * count
            else:
                current_string.append(char)
                
        return "".join(current_string)

#include <string>
#include <stack>
#include <cctype>

class Solution {
public:
    std::string decodeString(std::string s) {
        std::stack<int> countStack;
        std::stack<std::string> stringStack;
        std::string currentString = "";
        int k = 0;

        for (char c : s) {
            if (std::isdigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(k);
                stringStack.push(currentString);
                currentString = "";
                k = 0;
            } else if (c == ']') {
                std::string prevString = stringStack.top();
                stringStack.pop();
                int count = countStack.top();
                countStack.pop();
                
                std::string repeated = "";
                for (int i = 0; i < count; i++) {
                    repeated += currentString;
                }
                currentString = prevString + repeated;
            } else {
                currentString += c;
            }
        }
        return currentString;
    }
};

Complexity Analysis

• Time Complexity: O(l) where l is the length of the decoded string. We process each character and output the final decoded string.
• Space Complexity: O(l) auxiliary space to store elements in the stack and rebuild output substrings.

Where It Breaks

If the nested loop contains extremely large repetition values (e.g. 100000[...]), repeating the strings can exhaust heap memory limit.

Common Mistakes

• Incorrect multi-digit parsing: Parsing only single digits, which fails on inputs like 10[a] by repeating it only 0 or 1 times.
• State restoration mismatch: Forgetting to append the current string to the popped prefix from stringStack, which drops characters outside of brackets.

Frequently Asked Questions

Can we solve this using recursion? Yes. You can write a recursive helper function that takes an index pointer and returns the decoded string along with the end bracket position. Both stack and recursion approaches map to the same complexity.

How does this handle nested brackets? The double stack preserves the outer state when entering a nested bracket [, and restores it when exiting the inner bracket ].

← All Problems