Code Implementation

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        curr_num = 0
        curr_str = ""
        for c in s:
            if c.isdigit():
                curr_num = curr_num * 10 + int(c)
            elif c == "[":
                stack.append((curr_str, curr_num))
                curr_str = ""
                curr_num = 0
            elif c == "]":
                last_str, num = stack.pop()
                curr_str = last_str + curr_str * num
            else:
                curr_str += c
        return curr_str
      

class Solution {
public:
    string decodeString(string s) {
        stack> stk;
        string curr_str = "";
        int curr_num = 0;
        for (char c : s) {
            if (isdigit(c)) {
                curr_num = curr_num * 10 + (c - '0');
            } else if (c == '[') {
                stk.push({curr_str, curr_num});
                curr_str = "";
                curr_num = 0;
            } else if (c == ']') {
                auto p = stk.top(); stk.pop();
                string temp = "";
                for (int i = 0; i < p.second; ++i) temp += curr_str;
                curr_str = p.first + temp;
            } else {
                curr_str += c;
            }
        }
        return curr_str;
    }
};
      

class Solution {
    public String decodeString(String s) {
        Stack<String> strStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();
        String currStr = "";
        int currNum = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                currNum = currNum * 10 + (c - '0');
            } else if (c == '[') {
                strStack.push(currStr);
                numStack.push(currNum);
                currStr = "";
                currNum = 0;
            } else if (c == ']') {
                StringBuilder temp = new StringBuilder();
                int repeat = numStack.pop();
                for (int i = 0; i < repeat; i++) temp.append(currStr);
                currStr = strStack.pop() + temp.toString();
            } else {
                currStr += c;
            }
        }
        return currStr;
    }
}
      

var decodeString = function(s) {
    let stack = [];
    let currStr = "";
    let currNum = 0;
    for (let c of s) {
        if (!isNaN(c) && c !== ' ') {
            currNum = currNum * 10 + Number(c);
        } else if (c === "[") {
            stack.push([currStr, currNum]);
            currStr = "";
            currNum = 0;
        } else if (c === "]") {
            let [lastStr, num] = stack.pop();
            currStr = lastStr + currStr.repeat(num);
        } else {
            currStr += c;
        }
    }
    return currStr;
};
      

Problem Description

The Decode String problem asks you to decode a specially formatted input string s according to the following rules:

• Numbers followed by square brackets indicate repetition. For example, 3[a] means "repeat 'a' three times", resulting in aaa.
• Nested encodings are allowed, e.g., 2[abc3[cd]ef].
• The input string s consists of digits, letters, and square brackets, and is always a valid encoding (no malformed brackets or numbers).
• Your task is to decode s and return the resulting string.

Constraints:

• 1 ≤ s.length ≤ 30,000
• s contains only digits, English letters, '[', and ']'
• All input strings are valid; no need to handle invalid input.

Thought Process

At first glance, this problem looks similar to parsing mathematical expressions with parentheses, but with the twist that numbers now indicate repetition. A brute-force approach might try to repeatedly find the innermost brackets and expand them, but this would be inefficient and hard to manage for deeply nested strings.

To handle nested repetition, we need a way to keep track of what we're currently building and how many times to repeat it. Stacks are a natural fit for this, since they help us remember the context as we descend into deeper nested structures and then "pop" back out as we finish each one.

The main idea is to process the string character by character, using a stack to remember the current string and repeat count whenever we enter a new bracketed section. When we hit a closing bracket, we pop the stack, repeat the string, and append it to the previous context.

Solution Approach

• Initialize: Use a stack to keep track of previous strings and repeat counts. Use variables to build the current substring and current number.
• Iterate over each character in s:
  • If it's a digit, update the current number (taking care of multi-digit numbers).
  • If it's an opening bracket '[':
    • Push the current string and current number onto the stack.
    • Reset the current string and current number.
  • If it's a closing bracket ']':
    • Pop the last string and number from the stack.
    • Repeat the current string by the number popped, and append it to the last string.
    • This becomes the new current string.
  • If it's a letter, append it to the current string.
• Return: After processing the string, the current string variable holds the decoded result.

We use a stack because it allows us to easily "go back" to the previous context whenever we finish decoding a nested section. This approach works efficiently even for deeply nested or long input strings.

Example Walkthrough

Let's walk through the example s = "3[a2[c]]":

1. Read '3': Set current number to 3.
2. Read '[': Push ("", 3) onto the stack. Reset current string and number.
3. Read 'a': Current string becomes "a".
4. Read '2': Set current number to 2.
5. Read '[': Push ("a", 2) onto the stack. Reset current string and number.
6. Read 'c': Current string becomes "c".
7. Read ']': Pop ("a", 2). Repeat "c" 2 times to get "cc". Append to "a" → "acc".
8. Read ']': Pop ("", 3). Repeat "acc" 3 times to get "accaccacc".

The final decoded string is accaccacc.

Time and Space Complexity

• Brute-force approach: If we repeatedly search for innermost brackets and expand them, each expansion could scan the whole string, leading to O(N^2) time in the worst case for long or deeply nested inputs.
• Optimized stack approach: We process each character once, and stack operations (push/pop) are O(1). Thus, the time complexity is O(N), where N is the length of the input string.
• Space complexity: In the worst case, the stack could hold O(N) elements (for deeply nested brackets), and the output string could also be O(N), so space complexity is O(N).

Summary

The Decode String problem is elegantly solved by using a stack to manage nested repetitions. By carefully tracking the current string and repeat count at each level, we can efficiently and cleanly decode even complex nested encodings in a single pass. The stack-based approach is both intuitive and optimal, making it a great example of how classic data structures can simplify seemingly complex parsing tasks.