Approach: Stack of counts and strings

def decodeString(s):
    st = []; cur = ""; num = 0
    for c in s:
        if c.isdigit(): num = num*10 + int(c)
        elif c == "[": st.append((cur, num)); cur = ""; num = 0
        elif c == "]":
            prev, k = st.pop(); cur = prev + cur*k
        else: cur += c
    return cur

Complexity: O(output) time, O(output) space.

Full Solution — all languages

class Solution:
    def decodeString(self, s):
        st = []
        cur = ""
        num = 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == "[":
                st.append((cur, num))
                cur = ""
                num = 0
            elif c == "]":
                prev, k = st.pop()
                cur = prev + cur * k
            else:
                cur += c
        return cur

import java.util.*;
class Solution {
    public String decodeString(String s) {
        Deque<String> strs = new ArrayDeque<>();
        Deque<Integer> nums = new ArrayDeque<>();
        StringBuilder cur = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            else if (c == '[') {
                strs.push(cur.toString());
                nums.push(num);
                cur = new StringBuilder();
                num = 0;
            } else if (c == ']') {
                int k = nums.pop();
                StringBuilder tmp = new StringBuilder(strs.pop());
                for (int i = 0; i < k; i++) tmp.append(cur);
                cur = tmp;
            } else cur.append(c);
        }
        return cur.toString();
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: string decodeString(string s) {
        vector<string> strs;
        vector<int> nums;
        string cur;
        int num = 0;
        for (char c : s) {
            if (isdigit(c)) num = num * 10 + (c - '0');
            else if (c == '[') {
                strs.push_back(cur);
                nums.push_back(num);
                cur = "";
                num = 0;
            } else if (c == ']') {
                int k = nums.back();
                nums.pop_back();
                string prev = strs.back();
                strs.pop_back();
                string rep;
                for (int i = 0; i < k; i++) rep += cur;
                cur = prev + rep;
            } else cur += c;
        }
        return cur;
    }
};

/**
 * @param {string} s
 * @return {string}
 */ var decodeString = function(s) {
    const st = [];
    let cur = "", num = 0;
    for (const c of s) {
        if (c >= '0' && c <= '9') num = num * 10 + (+c);
        else if (c === '[') {
            st.push([cur, num]);
            cur = "";
            num = 0;
        } else if (c === ']') {
            const [prev, k] = st.pop();
            cur = prev + cur.repeat(k);
        } else cur += c;
    }
    return cur;
};

Decode String

Example 1

Example 2

Constraints