Medium Text
String Decoder
Receives a string encoded in the run-length format n[substring], where a number followed by a bracketed group means that group repeats n times, and groups can be nested. It scans the text left to right with a stack: digits build the repeat count, an opening bracket pushes the text built so far together with its count, plain letters are appended to the current text, and a closing bracket pops the saved text and count to repeat the just-finished group — expanding the innermost groups first. Returns the fully expanded string; text without brackets is returned unchanged and an empty input yields an empty string.
Visualization
- Input
- Result
Algorithm code
// String Decoder — a single pure function. Expands a string encoded in the
// run-length format `n[substring]` (groups may be nested) by scanning it once
// with two parallel stacks: one for pending repeat counts, one for the text
// built before each group. Internal state only; no side effects.
/**
* @param {string} s - the encoded string, e.g. "3[a2[c]]"
* @returns {string} the fully expanded string, e.g. "accaccacc"
*/
export function decodeString(s) {
const countStack = [];
const textStack = [];
let current = "";
let count = 0;
for (const ch of s) {
if (ch >= "0" && ch <= "9") {
count = count * 10 + Number(ch);
} else if (ch === "[") {
countStack.push(count);
textStack.push(current);
count = 0;
current = "";
} else if (ch === "]") {
const repeat = countStack.pop();
const previous = textStack.pop();
current = previous + current.repeat(repeat);
} else {
current += ch;
}
}
return current;
}FUNCTION decodeString(s):
countStack ← empty stack
textStack ← empty stack
current ← ""
count ← 0
FOR EACH ch IN s:
IF ch is a digit:
count ← count × 10 + digit(ch)
ELSE IF ch = '[':
PUSH count ONTO countStack
PUSH current ONTO textStack
count ← 0
current ← ""
ELSE IF ch = ']':
repeat ← POP countStack
previous ← POP textStack
current ← previous + repeat(current, repeat)
ELSE:
current ← current + ch
RETURN current