Decode String

medium string stack

Problem

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. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k.

Inputs = "2[a3[b]]"

Output"abbbabbb"

Inner 3[b] expands to "bbb"; then 2[abbb] expands to "abbbabbb".

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

function decodeString(s) {
  const stack = []; let cur = "", num = 0;
  for (const c of s) {
    if (/\d/.test(c)) num = num * 10 + Number(c);
    else if (c === '[') { stack.push([num, cur]); num = 0; cur = ""; }
    else if (c === ']') { const [k, prev] = stack.pop(); cur = prev + cur.repeat(k); }
    else cur += c;
  }
  return cur;
}

class Solution {
    public String decodeString(String s) {
        Deque<Object[]> stack = 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 == '[') { stack.push(new Object[]{ num, cur }); num = 0; cur = new StringBuilder(); }
            else if (c == ']') { Object[] f = stack.pop(); int k = (int) f[0]; StringBuilder prev = (StringBuilder) f[1]; StringBuilder rep = new StringBuilder(); for (int i = 0; i < k; i++) rep.append(cur); cur = prev.append(rep); }
            else cur.append(c);
        }
        return cur.toString();
    }
}

string decodeString(string s) {
    stack<pair<int, string>> st;
    string cur = "";
    int num = 0;
    for (char c : s) {
        if (isdigit(c)) num = num * 10 + (c - '0');
        else if (c == '[') { st.push({ num, cur }); num = 0; cur = ""; }
        else if (c == ']') { auto [k, prev] = st.top(); st.pop(); string rep; for (int i = 0; i < k; i++) rep += cur; cur = prev + rep; }
        else cur += c;
    }
    return cur;
}

Explanation

Encoded strings like 3[a2[c]] can nest, so we need to remember the work in progress each time we step into a new bracket. A stack of (count, partial-string) frames does exactly that.

We scan with two running values: num (the repeat count being read) and cur (the string built so far at the current level). Digits build up num. Plain letters are appended to cur.

On '[' we push the pair (num, cur) and reset both to start a fresh inner string. On ']' we pop back the saved (k, prev) and set cur = prev + cur * k — repeating the inner piece k times and gluing it after the saved prefix.

Example: "2[a3[b]]". The inner 3[b] becomes "bbb", making cur = "abbb"; then the outer 2[...] repeats it to "abbbabbb".

Every character drives one simple action, so we build the answer in a single left-to-right pass.

Time: O(|output|) Space: O(depth · max chunk)