Decode String

How it works

Using two separate stacks provides cleaner logic: one stack for accumulated strings and another for repeat counts. When we see [, we save the current string and count, then start fresh. When we see ], we pop the previous string and count, repeat the current string, and concatenate. This approach avoids the overhead of extracting digits and substrings from a mixed stack.

Steps

1. Initialize two stacks: one for strings (stringStack) and one for counts (countStack).
2. Maintain a current string cur and a current multiplier k.
3. Iterate through each character:
   • If it's a digit, update k = k * 10 + digit.
   • If it's [, push cur and k onto their respective stacks, then reset cur to empty and k to 0.
   • If it's ], pop the previous string and count. Set cur to the popped string plus the current string repeated by the popped count.
   • Otherwise, append the character to cur.
4. Return cur as the final decoded string.

Complexity

• Time complexity: O(n + N)
• Space complexity: O(n + N)

Where n is the length of the input string and N is the length of the output string.

Things to watch for

Multi-Digit Numbers

The repeat count k can be more than one digit (e.g., "12[a]" means repeat 'a' 12 times). A common mistake is treating only single digits.

Not Resetting the Repeat Count

After processing a [, the repeat count k must be reset to 0 for the next pattern. Forgetting this causes incorrect multiplications in nested structures.

Index Management in Recursion

When using recursion with a shared index, incrementing i at the wrong time causes characters to be skipped or processed twice. The index should be incremented after processing [ but before the recursive call.

class Solution:
    def decodeString(self, s: str) -> str:
        string_stack = []
        count_stack = []
        cur = ""
        k = 0

        for c in s:
            if c.isdigit():
                k = k * 10 + int(c)
            elif c == "[":
                string_stack.append(cur)
                count_stack.append(k)
                cur = ""
                k = 0
            elif c == "]":
                temp = cur
                cur = string_stack.pop()
                count = count_stack.pop()
                cur += temp * count
            else:
                cur += c

        return cur

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

        for (char c : s) {
            if (isdigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                stringStack.push_back(cur);
                countStack.push_back(k);
                cur = "";
                k = 0;
            } else if (c == ']') {
                string temp = cur;
                cur = stringStack.back();
                stringStack.pop_back();
                int count = countStack.back();
                countStack.pop_back();
                for (int i = 0; i < count; i++) {
                    cur += temp;
                }
            } else {
                cur += c;
            }
        }

        return cur;
    }
};