Decode encoded string: k[encoded_string] means encoded_string repeated k times.
Input: s="3[a]2[bc]" → Output: "aaabcbc"
Input: s="3[a2[c]]" → Output: "accaccacc"
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
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)