Decode a nested run-length string such as `3[a2[bc]]` to `abcbcabcbcabcbc`.
intermediateCore Java › Strings & Regular Expressions
Use two stacks: one for pending repeat counts and one for the string built before each [. On ], pop both, append the current segment count times to the saved prefix, and continue. Time is proportional to the output length.
static String decode(String s) {
Deque<Integer> counts = new ArrayDeque<>();
Deque<StringBuilder> prefixes = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
int k = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) k = k * 10 + (ch - '0');
else if (ch == '[') { counts.push(k); prefixes.push(cur); cur = new StringBuilder(); k = 0; }
else if (ch == ']') {
StringBuilder prev = prefixes.pop();
for (int i = counts.pop(); i > 0; i--) prev.append(cur);
cur = prev;
} else cur.append(ch);
}
return cur.toString();
}decode("3[a2[bc]]") returns abcbcabcbcabcbc; decode("10[x]") handles multi-digit counts through k * 10.
⚠ Follow-up traps
- Why
ArrayDequerather thanStack?Stackis a synchronizedVectorsubclass;ArrayDequeis the recommended unsynchronized stack. - What if the interviewer bans collections (Zoho style)? Recurse on an index: parse digits, skip
[, recurse until], repeat the returned string; the call stack replaces the explicit stacks. - Can the output explode? Yes,
99[99[99[a]]]is about 970k characters, so validate or cap the expanded size on untrusted input.
Asked at Zoho ChennaiCisco Bangalore