---

1. Problem Summary

You are given an encoded string s that follows a specific pattern, and your task is to decode it.

The encoding rules are:

k[encoded_string]

Where:

• k is a positive integer indicating how many times the enclosed substring repeats
• Brackets may be nested
• Characters may include lowercase letters
• Input is always valid and well-formed

Example interpretation:
Input:

"3[a2]"

Decoding steps:

• 2 → "cc"
• a" + "cc" → "acc"
• 3 * "acc" → "accaccacc"

Final output:

"accaccacc"

---

2. Key Insights

Nested encodings require a stack-based solution

You cannot decode from left to right in a single pass without remembering context.

Two types of state must be tracked:

1. Number multipliers (k)
2. Previously built partial strings

When encountering characters:

• digit → build repetition count
• [ → push current state to stack and reset trackers
• letter → append to current string
• ] → pop from stack, repeat substring, append

Stack enables proper handling of nested brackets

Each new [ introduces a new decoding context layer.

---

3. Approach

Iterative Stack-Based Decoding

We maintain:

• countStack to remember repetition counts
• stringStack to remember previous substrings
• currentString to accumulate characters in current level
• currentCount to build multi-digit numbers

Steps:

1. Initialize empty stacks and reset trackers
2. Loop through each character in s
3. If digit: currentCount = currentCount * 10 + digit
4. If ‘[‘:
   • push currentString onto stringStack
   • push currentCount onto countStack
   • reset currentString and currentCount
5. If letter: currentString += letter
6. If ‘]’:
   • pop repeat count
   • pop previous string
   • currentString = previous + currentString repeated count times
7. Continue until end
8. Return currentString

---

4. Time and Space Complexity

Time Complexity: O(N)

Every character is processed once and string expansion proportional to decoded output.

Space Complexity: O(N)

Stacks and resulting decoded string stored in memory.

---

5. Java Solution

import java.util.*;

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> stringStack = new Stack<>();
        
        StringBuilder currentString = new StringBuilder();
        int currentCount = 0;
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                currentCount = currentCount * 10 + (c - '0');
            } else if (c == '[') {
                countStack.push(currentCount);
                stringStack.push(currentString.toString());
                currentCount = 0;
                currentString = new StringBuilder();
            } else if (c == ']') {
                int repeat = countStack.pop();
                StringBuilder temp = new StringBuilder(stringStack.pop());
                
                for (int i = 0; i < repeat; i++) {
                    temp.append(currentString);
                }
                
                currentString = temp;
            } else {
                currentString.append(c);
            }
        }
        
        return currentString.toString();
    }
}

---

6. Dry Run Examples

Example 1

Input:

"3[a]2[bc]"

Processing:

1. 3[a] → “aaa”
2. 2[bc] → “bcbc”
3. combine → "aaabcbc"

Output:

"aaabcbc"

---

Example 2

Input:

"3[a2]"

Inner:

2 → "cc"

Then:

a + "cc" → "acc"

Then repeat:

3 * "acc" → "accaccacc"

Output:

"accaccacc"

---

Example 3

Input:

"2[abc]3[cd]ef"

Decoding:

• "abcabc"
• "cdcdcd"
• concatenated with "ef"

Output:

"abcabccdcdcdef"

---

Example 4

Input:

"10[a]"

Repeat ten times:

Output:

"aaaaaaaaaa"

---

Example 5 (nested deeper)

Input:

"2[x3[y2[z]]]"

Expand innermost:

2[z] → "zz"
y + "zz" → "yzz"
3 repetitions → "yzzyzzyzz"
x + that → "xyzzyzzyzz"
repeat twice → "xyzzyzzyzzxyzzyzzyzz"

Output:

"xyzzyzzyzzxyzzyzzyzz"

---

7. Why This Solution Works

• Correctly handles nested repetition
• Stack maintains decoding state
• Supports multi-digit repeat counts
• Efficient and linear processing
• Avoids recursion depth risks

---

8. Common Mistakes

1. Forgetting multi-digit numbers like "12[a]"
2. Attempting direct expansion without tracking nesting context
3. Using string concatenation inefficiently instead of StringBuilder
4. Misplacing repetition when popping from stack
5. Assuming encoding depth is flat (it can be nested arbitrarily)