Decode String

Practice Link

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. k is guaranteed to be a positive integer, the input is always valid (well-formed brackets, no stray digits in the actual data), and the decoded output length never exceeds 10^5.

Intuition#

Brackets nest (3[a2[c]]), so this is naturally a stack problem — every time you enter a new [...], you need to "pause" whatever string you were building outside it, and resume building it once the matching ] closes. That pause/resume behavior is exactly what a stack gives you for free.

Walking through the string, only three things ever happen:

• A digit: accumulate it into num (handles multi-digit k, e.g. 12[...], digit by digit: num = num*10 + digit).
• A [: everything built so far in res belongs to the outer context, and num is the repeat count for what comes next. Push both onto the stack as a pair, then reset res and num to start fresh for the inner content.
• A ]: the inner content just finished. Repeat res (the inner string) k times — k being whatever repeat count was pushed alongside this bracket — then glue it onto the string that was paused when we entered this bracket (popped from the stack). That becomes the new res, and the stack pops back to the outer context.
• Any other character: just append it to res — it's a literal part of the current string.

By the end, everything has unwound back to the outermost context and res holds the fully decoded string.

Both solutions below implement exactly this — they differ only in how the paused (string, count) context is stored.

Approach 1: Two Parallel Stacks#

class Solution {
public:
    string decodeString(string s) {
        stack<string> stk1;
        stack<int> stk2;
        int num = 0;
        string res = "";

        for(int i=0;i<s.size();i++){
            if(isdigit(s[i])){
                num = num*10 + s[i] - '0';
            }else if(s[i] == '['){
                stk1.push(res);
                stk2.push(num);
                num = 0;
                res = "";
            }else if(s[i] == ']'){
                string temp = res;
                for(int i=1;i<stk2.top();i++){
                    temp += res;
                }
                res = stk1.top() + temp;
                stk1.pop();
                stk2.pop();
            }else{
                res += s[i];
            }
        }
        return res;
    }
};

stk1 holds the paused outer strings, stk2 holds their matching repeat counts — the two are kept in sync manually (every push/pop happens to both together).

Approach 2: Single Stack of Pairs#

class Solution {
public:
    string decodeString(string s) {
        stack<pair<string,int>> stk;
        int num = 0;
        string res = "";

        for(int i=0;i<s.size();i++){
            if(isdigit(s[i])){
                num = num*10 + s[i] - '0';
            }else if(s[i] == '['){
                stk.push({res, num});
                num = 0;
                res = "";
            }else if(s[i] == ']'){
                string temp = res;
                for(int i=1;i<stk.top().second;i++){
                    temp += res;
                }
                res = stk.top().first + temp;
                stk.pop();
            }else{
                res += s[i];
            }
        }
        return res;
    }
};

Same logic as approach 1, but the outer string and its repeat count are bundled into one pair<string,int> and pushed/popped as a single unit. This is the safer version of the two — with two separate stacks it's possible to accidentally push/pop them out of sync (e.g. forgetting one of the two calls); bundling into a pair makes that class of bug structurally impossible.

Dry Run#

s = "3[a2[c]]", expected output "accaccacc".

Final res = "accaccacc".

Complexities#

Let n = length of the final decoded string (bounded by 10^5 per the constraints).

Time Complexity: O(n) — every character in the output is produced by a bounded number of concatenation operations tied to its nesting depth; the repeated-concatenation cost at each ] telescopes across the whole string to the size of the final decoded output.

Space Complexity: O(n) — for the stack (holding paused strings/counts across nested brackets) and the output string itself.