Course4all

Decode String

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

Decode String

Decode an encoded string where k[encoded_string] means encoded_string is repeated k times.

Visual Representation

s = "3[a]2[bc]" 1. '3': k = 3 2. '[': Push 3, Push "". Stack: [(3, "")] 3. 'a': curr = "a" 4. ']': Pop 3. res = "" + "a"*3 = "aaa" 5. '2': k = 2 6. '[': Push 2, Push "aaa". Stack: [(2, "aaa")] 7. "bc": curr = "bc" 8. ']': Pop 2. res = "aaa" + "bc"*2 = "aaabcbc"
Medium

Examples

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

Level I: Brute Force (Innermost Bracket First)

Intuition

Find the innermost [] bracket pair using regex or string searching, expand it (repeat the inner string by the preceding number), replace it in the original string, and repeat until no brackets remain. This naturally handles nested brackets by working from inside out.
⏱ O(N * maxK) — each pass expands one bracket group, and there can be N/2 groups.💾 O(N * maxK) for the expanded string.
java
import java.util.regex.*;

public class Main {
    public static String decodeString(String s) {
        Pattern p = Pattern.compile("(\\d+)\\[([a-z]*)\\]");
        Matcher m;
        while ((m = p.matcher(s)).find()) {
            int k = Integer.parseInt(m.group(1));
            StringBuilder rep = new StringBuilder();
            for (int i = 0; i < k; i++) rep.append(m.group(2));
            s = s.substring(0, m.start()) + rep + s.substring(m.end());
        }
        return s;
    }
    public static void main(String[] args) {
        System.out.println(decodeString("3[a]2[bc]")); // aaabcbc
    }
}
Approach 2

Level III: Optimal (Two Stacks)

Intuition

Use two stacks: one to store the multipliers (countStack) and one to store the strings built so far (resStack). When an opening bracket [ is met, push the current count and current string. When a closing bracket ] is met, pop the multiplier and the previous string, then append the repeated current string to the previous one.
⏱ O(N * maxK)💾 O(N)

Detailed Dry Run

CharcountStackresStackcurrStr
'3'[][]"" (k=3)
'['[3][""]""
'a'[3][""]"a"
']'[][]"aaa"
java
import java.util.*;

public class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> resStack = new Stack<>();
        StringBuilder cur = new StringBuilder();
        int k = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) k = k * 10 + (c - '0');
            else if (c == '[') {
                countStack.push(k);
                resStack.push(cur);
                cur = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                StringBuilder tmp = cur;
                cur = resStack.pop();
                int count = countStack.pop();
                while (count-- > 0) cur.append(tmp);
            } else cur.append(c);
        }
        return cur.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.decodeString("3[a]2[bc]")); // "aaabcbc"
    }
}

⚠️ Common Pitfalls & Tips

Multi-digit numbers (like 100[a]) must be handled. Nested brackets are naturally handled by the stack.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionBasic Calculator II
Next Question →Remove Duplicate Letters