Course4all
Join us on telegram
Home/dsa/Stack/Decode String

Decode String

Master this topic with zero to advance depth.

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.

← Previous QuestionBasic Calculator II
Next Question →Remove Duplicate Letters