Decode String

Decode encoded string: k[encoded_string] means encoded_string repeated k times.

Example 1

Input: s="3[a]2[bc]" → Output: "aaabcbc"

Example 2

Input: s="3[a2[c]]" → Output: "accaccacc"

Solution Approach

Use two stacks: one for repeat counts, one for string builders. Process character by character.

Stack for counts, stack for string builders
On digit: accumulate number
On [: push current count and current sb, reset both
On ]: pop count and previous sb, append current sb repeated count times
On letter: append to current sb

Java

public String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> builders = new ArrayDeque<>();
    StringBuilder curr = new StringBuilder();
    int num = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) num = num * 10 + (c - '0');
        else if (c == '[') { counts.push(num); builders.push(curr); curr = new StringBuilder(); num = 0; }
        else if (c == ']') {
            int k = counts.pop();
            StringBuilder prev = builders.pop();
            String repeated = curr.toString().repeat(k);
            prev.append(repeated);
            curr = prev;
        } else curr.append(c);
    }
    return curr.toString();
}

Time Complexity: O(n * max_k)
Space Complexity: O(n)