Decode Ways: Count All Decodings of a Digit Sequence

Counting all valid ways to decode a digit string into letters, where 1 maps to A and 26 maps to Z, is a dynamic programming problem that appears often in placement coding rounds at product companies.

This article covers the canonical decode ways problem end to end: the encoding rules, edge cases that eliminate decodings entirely, a recursive solution with its complexity trade-off, and a bottom-up DP solution that runs in O(n) time. Pairing this with related digit manipulation practice builds a solid base for the array-and-string section of coding interviews.

The mapping and problem statement

The encoding maps each integer from 1 to 26 to a letter:

• 1 maps to A, 2 maps to B, 3 maps to C, and so on through 9 mapping to I
• 10 maps to J, 11 maps to K, 12 maps to L, continuing through 26 mapping to Z

Given a string of digits (no spaces, no letters), count how many distinct letter strings it decodes to. Two decoded strings count as distinct if they differ in at least one position.

Worked example 1 — input “123”

Valid decodings:

• “ABC” reads as 1, 2, 3
• “LC” reads as 12, 3
• “AW” reads as 1, 23

Output: 3

Worked example 2 — input “121”

Valid decodings:

• “ABA” reads as 1, 2, 1
• “AU” reads as 1, 21
• “LA” reads as 12, 1

Output: 3

Edge cases that trip candidates

Zero handling is where most submitted solutions fail. Three patterns are worth internalising before the interview.

Leading zero

• Input: "06" — Output: 0
• Reason: ‘0’ has no single-character mapping. A string starting with ‘0’ has no valid full decoding. The DP base case returns 0 immediately.

Internal zero preceded by 3 or higher

• Input: "30" — Output: 0
• Reason: ‘3’ alone maps to C, and ‘0’ alone is invalid. The pair ‘30’ equals 30, which is outside the valid range 10 to 26, so no two-digit decode exists either. Both paths hit a dead end.

Internal zero preceded by 1 or 2

• Input: "10" — Output: 1. The pair ‘10’ maps to J. Single decoding only.
• Input: "20" — Output: 1. The pair ‘20’ maps to T. Single decoding only.
• Input: "100" — Output: 0. ‘10’ decodes to J, but the trailing ‘0’ cannot decode alone, and ‘00’ (pair of the last two) equals 0, which is outside [10, 26]. No valid full decoding.

These three patterns cover almost every zero-related bug in candidate submissions. Once they are handled correctly, the recurrence itself is straightforward.

Recursive approach

The recursive idea: a string of n digits decodes by either taking the last single digit as a character (valid if the digit is 1 through 9), or taking the last two digits as a pair (valid if the pair is in [10, 26]), or both. Add all contributions to get the total count.

#include <iostream>
#include <string>
using namespace std;

int countDecodings(string digits, int n) {
    if (n == 0 || n == 1) return 1;
    if (digits[0] == '0') return 0;

    int count = 0;

    // Single-digit decode: last character must be non-zero
    if (digits[n - 1] > '0')
        count = countDecodings(digits, n - 1);

    // Two-digit decode: pair must be in [10, 26]
    if (digits[n - 2] == '1' ||
        (digits[n - 2] == '2' && digits[n - 1] < '7'))
        count += countDecodings(digits, n - 2);

    return count;
}

int main() {
    string digits = "121";
    cout << "Total Decodings: " << countDecodings(digits, digits.size());
    return 0;
}

Complexity:

• Time: O(2^n). Each call branches into up to two sub-calls, and sub-problems overlap without sharing results.
• Space: O(n) call stack depth in the worst case.

Adding a memoisation cache converts this to O(n) time. The recursive structure stays identical: add a lookup before branching and store the result before returning. The space complexity analysis article covers the call-stack vs. memo-array trade-off in detail.

Dynamic programming approach

The bottom-up DP builds the answer without a call stack. Define dp[i] as the number of ways to decode the first i characters of the string.

Base cases:

• dp[0] = 1 (empty prefix, used as a seed for the recurrence)
• dp[1] = 1 if digits[0] is not ‘0’, else 0

Recurrence for i from 2 to n:

• Single-digit step: if digits[i-1] is not ‘0’, add dp[i-1] to dp[i]
• Two-digit step: if the pair formed by digits[i-2] and digits[i-1] falls in [10, 26], add dp[i-2] to dp[i]

class DecodeWays {
    static int countDecodings(String digits) {
        int n = digits.length();
        if (n == 0 || digits.charAt(0) == '0') return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            // Single-digit step
            if (digits.charAt(i - 1) > '0')
                dp[i] = dp[i - 1];

            // Two-digit step
            int twoDigit = Integer.parseInt(digits.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(countDecodings("123")); // 3
    }
}

Trace for input “123”

• Start: dp[0] = 1, dp[1] = 1
• i=2: digit ‘2’ is nonzero, so dp[2] = dp[1] = 1; pair “12” equals 12, in [10, 26], so dp[2] += dp[0] giving dp[2] = 2
• i=3: digit ‘3’ is nonzero, so dp[3] = dp[2] = 2; pair “23” equals 23, in [10, 26], so dp[3] += dp[1] giving dp[3] = 3
• Return dp[3] = 3 — correct

Complexity summary

Approach	Time	Space
Recursion (no memo)	O(2^n)	O(n) call stack
Recursion with memoisation	O(n)	O(n)
DP with array	O(n)	O(n)
DP with two variables	O(n)	O(1)

The O(1) space variant replaces the dp[] array with two scalar variables. At each step, shift prev2 = prev1 and prev1 = current. The GeeksforGeeks walkthrough covers this two-variable form. For interview purposes, explain the array version first and mention the optimisation as a follow-up. Interviewers at product companies commonly ask for it after the O(n) solution is accepted.

The same pattern of scanning two DP values per step also appears in the equilibrium index problem, where prefix and suffix sums are tracked in parallel. Recognising this family of problems speeds up setup time for similar questions in coding rounds.

From digit decoding to LLM tokenisation

The decode-ways recurrence counts how many ways a linear sequence can be split into valid segments from a fixed alphabet. That is exactly what a language-model tokeniser does: given a byte stream, enumerate valid splits into sub-word tokens from a fixed vocabulary. The two problems share the same DP structure. The only difference is alphabet size (26 symbols here vs. tens of thousands of tokens) and the validity rule.

Once the decode-ways recurrence is clear, the mental leap to understanding tokeniser constraints is a small one. For counting problems and sequence-splitting generally, building intuition across a few concrete DP exercises is faster than reading theory in isolation.

TinkerLLM is a self-paced playground where you can run real tokeniser experiments on live LLMs for ₹299, a concrete way to see the same counting logic from this problem working on natural-language input rather than digit strings. If the decode-ways recurrence clicked, the tokenisation demos will too.