Pattern Guide
String Decode & Transform Patterns
"Decode encoded strings, run-length encoding, parenthesis-based nesting."
String decode problems parse encoded formats: "3[ab]" → "ababab", run-length encoding/decoding, nested bracket expansion, and custom encodings. Core tool: stack-based parsing — push current string and repeat count on "[", pop and repeat on "]". Variants: multiple nesting levels, nested multipliers, recursive descent for complex grammars.
Problems you can solve with this pattern
4 problems · click any to start solving
// Decode "3[ab2[c]]" → "ababcc"
function decodeString(s) {
const stack = []; // [{str, k}]
let current = '', k = 0;
for (const c of s) {
if (c >= '0' && c <= '9') {
k = k * 10 + parseInt(c); // handle multi-digit numbers
} else if (c === '[') {
stack.push({str: current, k}); // save context
current = ''; k = 0; // reset for inner string
} else if (c === ']') {
const {str, k: times} = stack.pop();
current = str + current.repeat(times); // expand inner
} else {
current += c;
}
}
return current;
}
// Run-length encoding
function encode(s) {
let result = '', count = 1;
for (let i = 1; i <= s.length; i++) {
if (i < s.length && s[i] === s[i-1]) count++;
else { result += (count > 1 ? count : '') + s[i-1]; count = 1; }
}
return result;
}Decode string with nested brackets: iterate characters. On digit: parse full number. On "[": push (current_string, current_count) to stack, reset. On "]": pop (prev_string, count), current_string = prev_string + current_string.repeat(count). On letter: append to current_string. Stack maintains the "context" at each nesting level.
// Decode "3[ab2[c]]" → "ababcc"
function decodeString(s) {
const stack = []; // [{str, k}]
let current = '', k = 0;
for (const c of s) {
if (c >= '0' && c <= '9') {
k = k * 10 + parseInt(c); // handle multi-digit numbers
} else if (c === '[') {
stack.push({str: current, k}); // save context
current = ''; k = 0; // reset for inner string
} else if (c === ']') {
const {str, k: times} = stack.pop();
current = str + current.repeat(times); // expand inner
} else {
current += c;
}
}
return current;
}
// Run-length encoding
function encode(s) {
let result = '', count = 1;
for (let i = 1; i <= s.length; i++) {
if (i < s.length && s[i] === s[i-1]) count++;
else { result += (count > 1 ? count : '') + s[i-1]; count = 1; }
}
return result;
}1. On "[": push (current_string, current_multiplier) to stack; reset current
2. On "]": pop (prev, k); current = prev + current.repeat(k)
3. On digit: build multiplier (k = k*10 + digit) for multi-digit numbers
4. On letter: append to current
Encoding schemes:
- Run-length: "aabbbcc" → "a2b3c2" (or "2a3b2c" depending on format)
- Length-prefix: "length#string" — safe for any content
- Delimiter: works only if delimiter doesn't appear in content
Recursive descent: For complex grammars, implement explicit recursive functions for each grammar rule instead of a single-pass stack.