Algorithm Day72 - Decode String

Posted on In , Views:

🧩 Problem Description

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.
Note that k is guaranteed to be a positive integer.

💬 Examples

Example 1

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

Example 2

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

Example 3

1
2
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Example 4

1
2
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

💡 Intuition

We can use two stacks to decode the string:

  • One stack for numbers (repeat counts).
  • One stack for strings (previous built results).
  • Traverse the input string:
    • If digit → build number.
    • If [ → push current string and number to stacks.
    • If ] → pop count and previous string, repeat current substring and append.
    • Otherwise → append characters to current string.

🔢 Java Code (Stack Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;

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

⏱ Complexity Analysis

  • Time: O(n) — each character processed once.
  • Space: O(n) — stacks for numbers and strings.

✍️ Summary

  • Use two stacks: one for counts, one for partial strings.
  • Build substrings iteratively while handling nested brackets.

Related problems

  • lc-224 — Basic Calculator
  • lc-227 — Basic Calculator II
  • lc-20 — Valid Parentheses