A message was encoded by mapping each letter to its position in the alphabet — A to 1, B to 2, all the way to Z to 26 — and then writing the numbers down with no separators. Given the resulting string of digits, return the number of distinct ways it could be decoded back into letters. This is the classic Decode Ways counting problem: you are not asked to list the decodings, only to count them.
function stringDecodeMessage(digits: string): number;
// digits is a string of '0'–'9' characters; returns a count of valid decodingsstringDecodeMessage("12"); // 2 — "1 2" → "AB", or "12" → "L"
stringDecodeMessage("226"); // 3 — "2 2 6" → "BBF", "22 6" → "VF", "2 26" → "BZ"
stringDecodeMessage("06"); // 0 — no decoding: "0" maps to nothing, and "06" is not a valid pair1–9. A two-digit chunk decodes only if it is 10–26. Anything outside those ranges contributes nothing."06" or "08" does not map to a letter — only "10" through "26" are valid two-digit chunks. 09 is not 9."0" has no decoding. stringDecodeMessage("0") returns 0, and any 0 that cannot be the second digit of a 10–26 pair kills every decoding that reaches it.stringDecodeMessage("") returns 1 — the empty string has exactly one decoding, the empty message. This is the base case the counting relies on; the solution explains why.You'll count how many distinct letter-strings could have produced a given run of digits, where A=1 through Z=26 were concatenated with no separators.
Someone wrote "HELLO" as 8 5 12 12 15 and then dropped the spaces: "85121215". Now you only see the digits, and the spaces are gone. How many different messages could have produced exactly these digits? At each position you face the same fork: peel off one digit as a letter (1–9 are A–I), or peel off two digits as a letter (10–26 are J–Z). Some forks are dead ends — 0 is not a letter on its own, and 27 is past Z. You want the count of complete, valid splits, not the splits themselves.
Think of decoding as walking left to right through the string, repeatedly choosing to consume one digit or two. Each choice that lands on a valid letter opens a branch; the branches form a tree, and every leaf that consumes the whole string is one valid decoding. Counting decodings is counting those leaves.
The single fact that makes the problem tractable: two different prefixes that leave the same suffix have the same number of ways to finish. Once you've decoded "22", the number of ways to finish "6" does not depend on whether you got there as "2","2" or as "22". That shared sub-problem is what we'll memoize.
The tree above translates directly into recursion. Define count(i) as "the number of ways to decode the suffix starting at index i." At each call, try consuming one digit, then try consuming two:
function stringDecodeMessage(digits) {
function count(i) {
if (i === digits.length) return 1; // consumed everything → one valid decoding
if (digits[i] === '0') return 0; // a chunk can't start with 0
let total = count(i + 1); // take one digit (1–9, guaranteed by the guard above)
const pair = digits.slice(i, i + 2);
if (pair.length === 2 && pair >= '10' && pair <= '26') {
total += count(i + 2); // take a valid two-digit chunk
}
return total;
}
return count(0);
}This is correct — it returns the right count for every input. The problem is speed. Look at the tree again: decoding "123" calls count on the suffix "3" along more than one path, and recomputes it from scratch each time. On a string of all 1s the call count follows the Fibonacci sequence — "1111111111" (ten ones) already fans out to over a hundred calls, and every added digit roughly multiplies the work. By thirty digits it's effectively hung.
The fix is to compute each sub-problem once and store it. We'll flip the recursion into a left-to-right table. Let ways[i] be the number of ways to decode the first i characters of the string. The answer is ways[n], where n is the length.
function stringDecodeMessage(digits) {
const n = digits.length;
// ways[i] = number of decodings of the first i characters.
const ways = new Array(n + 1).fill(0);
ways[0] = 1; // the empty prefix has exactly one decoding: the empty message
for (let i = 1; i <= n; i++) {
const one = digits[i - 1]; // the digit ending at position i
// Single-digit decode: valid only for 1–9. A leading '0' contributes nothing.
if (one >= '1' && one <= '9') {
ways[i] += ways[i - 1];
}
// Two-digit decode: only when the pair s[i-2..i-1] lands in 10–26.
if (i >= 2) {
const two = digits.slice(i - 2, i);
if (two >= '10' && two <= '26') {
ways[i] += ways[i - 2];
}
}
}
return ways[n];
}
module.exports = { stringDecodeMessage };Three shifts from the naive version. First, ways[i] is indexed by prefix length, not suffix start — so the loop runs once per position and each cell is written exactly once. Second, ways[0] = 1 is the base case the recursion expressed as count(length) === 1, re-pointed at the front: an empty prefix decodes one way, and that 1 is what every single-digit and two-digit term ultimately multiplies up from. Third, comparing two-character substrings with >= '10' && <= '26' works because JavaScript compares equal-length numeric strings the same way it would the numbers — "09" < "10" and "26" < "27" both hold lexicographically, which conveniently rejects the leading-zero pair too.
Trace "226". We build a ways array of length 4 (n + 1), seed ways[0] = 1, and fill left to right.
ways[0] = 1 — base case. The empty prefix decodes one way.i = 1, digit "2" — "2" is in 1–9, so ways[1] += ways[0] → 1. There's no pair yet (i < 2). ways[1] = 1.i = 2, digit "2", pair "22" — single digit "2" is valid: ways[2] += ways[1] → 1. The pair "22" is in 10–26: ways[2] += ways[0] → 2. So ways[2] = 2 (the decodings "BB" and "V").i = 3, digit "6", pair "26" — single digit "6" is valid: ways[3] += ways[2] → 2. The pair "26" is in 10–26: ways[3] += ways[1] → 3. So ways[3] = 3.Return ways[3] = 3 — matching "BBF", "VF", "BZ". Notice how each two-digit step reuses a value computed earlier (ways[1], ways[0]) instead of re-deriving it: that reuse is the whole point of the table.
"06" is not 6 — a two-digit chunk must be 10–26, and "06" is below 10. Likewise a single "0" is not a letter. If a 0 can't be the second digit of a valid 10–26 pair, every decoding passing through it dies. That's why stringDecodeMessage("100") returns 0: the final "0" can't stand alone, and "00" is not a valid pair.10–26, not 1–26. Single digits are handled by the other branch. The pair branch only fires for 10 and up — pairs like "07" are rejected by the lower bound, and "27"–"99" by the upper bound.27 is not decodable as a pair. "27" splits only as "2" then "7" → one way. People expect a second way from the pair, but 27 > 26, so the two-digit branch never adds anything.ways[0] = 1, not 0. This is the trap that breaks every count. If you seed it to 0, then ways[1] for a valid single digit becomes 0 + 0 = 0 and the whole array stays zero. The empty prefix must count as one decoding so the additions have something to build on — it's the multiplicative identity of the recurrence.digits.slice(i - 2, i) is a two-char string. You can compare it lexicographically (>= '10' && <= '26') because both bounds are two digits, or convert with Number(...) and compare numerically. Don't mix: Number("09") is 9, which would wrongly pass a >= 10 numeric check only if you forgot the leading-zero case — the string comparison rejects "09" cleanly because "09" < "10".1, not 0. The contract treats the empty message as one valid decoding, which is exactly ways[0]. Returning 0 here is a common off-by-one that also corrupts the base case reasoning above.decodings(i) returns an array of strings. This is no longer a counting problem — the output size is itself exponential, so it can't beat the naive recursion's time, but it's the natural next ask in an interview.* wildcard. A variant (LeetCode "Decode Ways II") lets * stand for any digit 1–9. Now each single-digit step can contribute up to 9 ways and each pair step has to count how many of *'s expansions land in 10–26. The DP shape is identical; only the per-step multipliers change, and you reduce modulo 1e9 + 7 because the counts explode.O(1) space. ways[i] only ever reads ways[i - 1] and ways[i - 2], so you can roll the whole array into two variables (prev, prevPrev) and update them as you scan. Same O(n) time, constant memory — the standard follow-up once the array version is working.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
A message was encoded by mapping each letter to its position in the alphabet — A to 1, B to 2, all the way to Z to 26 — and then writing the numbers down with no separators. Given the resulting string of digits, return the number of distinct ways it could be decoded back into letters. This is the classic Decode Ways counting problem: you are not asked to list the decodings, only to count them.
function stringDecodeMessage(digits: string): number;
// digits is a string of '0'–'9' characters; returns a count of valid decodingsstringDecodeMessage("12"); // 2 — "1 2" → "AB", or "12" → "L"
stringDecodeMessage("226"); // 3 — "2 2 6" → "BBF", "22 6" → "VF", "2 26" → "BZ"
stringDecodeMessage("06"); // 0 — no decoding: "0" maps to nothing, and "06" is not a valid pair1–9. A two-digit chunk decodes only if it is 10–26. Anything outside those ranges contributes nothing."06" or "08" does not map to a letter — only "10" through "26" are valid two-digit chunks. 09 is not 9."0" has no decoding. stringDecodeMessage("0") returns 0, and any 0 that cannot be the second digit of a 10–26 pair kills every decoding that reaches it.stringDecodeMessage("") returns 1 — the empty string has exactly one decoding, the empty message. This is the base case the counting relies on; the solution explains why.You'll count how many distinct letter-strings could have produced a given run of digits, where A=1 through Z=26 were concatenated with no separators.
Someone wrote "HELLO" as 8 5 12 12 15 and then dropped the spaces: "85121215". Now you only see the digits, and the spaces are gone. How many different messages could have produced exactly these digits? At each position you face the same fork: peel off one digit as a letter (1–9 are A–I), or peel off two digits as a letter (10–26 are J–Z). Some forks are dead ends — 0 is not a letter on its own, and 27 is past Z. You want the count of complete, valid splits, not the splits themselves.
Think of decoding as walking left to right through the string, repeatedly choosing to consume one digit or two. Each choice that lands on a valid letter opens a branch; the branches form a tree, and every leaf that consumes the whole string is one valid decoding. Counting decodings is counting those leaves.
The single fact that makes the problem tractable: two different prefixes that leave the same suffix have the same number of ways to finish. Once you've decoded "22", the number of ways to finish "6" does not depend on whether you got there as "2","2" or as "22". That shared sub-problem is what we'll memoize.
The tree above translates directly into recursion. Define count(i) as "the number of ways to decode the suffix starting at index i." At each call, try consuming one digit, then try consuming two:
function stringDecodeMessage(digits) {
function count(i) {
if (i === digits.length) return 1; // consumed everything → one valid decoding
if (digits[i] === '0') return 0; // a chunk can't start with 0
let total = count(i + 1); // take one digit (1–9, guaranteed by the guard above)
const pair = digits.slice(i, i + 2);
if (pair.length === 2 && pair >= '10' && pair <= '26') {
total += count(i + 2); // take a valid two-digit chunk
}
return total;
}
return count(0);
}This is correct — it returns the right count for every input. The problem is speed. Look at the tree again: decoding "123" calls count on the suffix "3" along more than one path, and recomputes it from scratch each time. On a string of all 1s the call count follows the Fibonacci sequence — "1111111111" (ten ones) already fans out to over a hundred calls, and every added digit roughly multiplies the work. By thirty digits it's effectively hung.
The fix is to compute each sub-problem once and store it. We'll flip the recursion into a left-to-right table. Let ways[i] be the number of ways to decode the first i characters of the string. The answer is ways[n], where n is the length.
function stringDecodeMessage(digits) {
const n = digits.length;
// ways[i] = number of decodings of the first i characters.
const ways = new Array(n + 1).fill(0);
ways[0] = 1; // the empty prefix has exactly one decoding: the empty message
for (let i = 1; i <= n; i++) {
const one = digits[i - 1]; // the digit ending at position i
// Single-digit decode: valid only for 1–9. A leading '0' contributes nothing.
if (one >= '1' && one <= '9') {
ways[i] += ways[i - 1];
}
// Two-digit decode: only when the pair s[i-2..i-1] lands in 10–26.
if (i >= 2) {
const two = digits.slice(i - 2, i);
if (two >= '10' && two <= '26') {
ways[i] += ways[i - 2];
}
}
}
return ways[n];
}
module.exports = { stringDecodeMessage };Three shifts from the naive version. First, ways[i] is indexed by prefix length, not suffix start — so the loop runs once per position and each cell is written exactly once. Second, ways[0] = 1 is the base case the recursion expressed as count(length) === 1, re-pointed at the front: an empty prefix decodes one way, and that 1 is what every single-digit and two-digit term ultimately multiplies up from. Third, comparing two-character substrings with >= '10' && <= '26' works because JavaScript compares equal-length numeric strings the same way it would the numbers — "09" < "10" and "26" < "27" both hold lexicographically, which conveniently rejects the leading-zero pair too.
Trace "226". We build a ways array of length 4 (n + 1), seed ways[0] = 1, and fill left to right.
ways[0] = 1 — base case. The empty prefix decodes one way.i = 1, digit "2" — "2" is in 1–9, so ways[1] += ways[0] → 1. There's no pair yet (i < 2). ways[1] = 1.i = 2, digit "2", pair "22" — single digit "2" is valid: ways[2] += ways[1] → 1. The pair "22" is in 10–26: ways[2] += ways[0] → 2. So ways[2] = 2 (the decodings "BB" and "V").i = 3, digit "6", pair "26" — single digit "6" is valid: ways[3] += ways[2] → 2. The pair "26" is in 10–26: ways[3] += ways[1] → 3. So ways[3] = 3.Return ways[3] = 3 — matching "BBF", "VF", "BZ". Notice how each two-digit step reuses a value computed earlier (ways[1], ways[0]) instead of re-deriving it: that reuse is the whole point of the table.
"06" is not 6 — a two-digit chunk must be 10–26, and "06" is below 10. Likewise a single "0" is not a letter. If a 0 can't be the second digit of a valid 10–26 pair, every decoding passing through it dies. That's why stringDecodeMessage("100") returns 0: the final "0" can't stand alone, and "00" is not a valid pair.10–26, not 1–26. Single digits are handled by the other branch. The pair branch only fires for 10 and up — pairs like "07" are rejected by the lower bound, and "27"–"99" by the upper bound.27 is not decodable as a pair. "27" splits only as "2" then "7" → one way. People expect a second way from the pair, but 27 > 26, so the two-digit branch never adds anything.ways[0] = 1, not 0. This is the trap that breaks every count. If you seed it to 0, then ways[1] for a valid single digit becomes 0 + 0 = 0 and the whole array stays zero. The empty prefix must count as one decoding so the additions have something to build on — it's the multiplicative identity of the recurrence.digits.slice(i - 2, i) is a two-char string. You can compare it lexicographically (>= '10' && <= '26') because both bounds are two digits, or convert with Number(...) and compare numerically. Don't mix: Number("09") is 9, which would wrongly pass a >= 10 numeric check only if you forgot the leading-zero case — the string comparison rejects "09" cleanly because "09" < "10".1, not 0. The contract treats the empty message as one valid decoding, which is exactly ways[0]. Returning 0 here is a common off-by-one that also corrupts the base case reasoning above.decodings(i) returns an array of strings. This is no longer a counting problem — the output size is itself exponential, so it can't beat the naive recursion's time, but it's the natural next ask in an interview.* wildcard. A variant (LeetCode "Decode Ways II") lets * stand for any digit 1–9. Now each single-digit step can contribute up to 9 ways and each pair step has to count how many of *'s expansions land in 10–26. The DP shape is identical; only the per-step multipliers change, and you reduce modulo 1e9 + 7 because the counts explode.O(1) space. ways[i] only ever reads ways[i - 1] and ways[i - 2], so you can roll the whole array into two variables (prev, prevPrev) and update them as you scan. Same O(n) time, constant memory — the standard follow-up once the array version is working.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.