Decode Ways: A Step-by-Step Dynamic Programming Interview Walkthrough

Interviewers reach for the Decode Ways dynamic programming problem when they want to see whether you can reason about validity, not just optimization. The recurrence itself is short, but every transition has a precondition, and a candidate who forgets to check those preconditions will count nonsense and not realize it. That's the actual test: can you define a state cleanly, validate every transition into it, and handle the boundary cases that break naive solutions?

Counting valid decodings of an ambiguous sequence is the same shape of problem that shows up in natural language tokenization (how many ways can a string be split into valid words?), bioinformatics (how many ways can a sequence be parsed into valid codons?), and any data format where boundaries between symbols aren't explicit, like decoding compressed or variable-length encodings.

Problem Statement

A message containing letters from A–Z is encoded using the following mapping:

• 'A' → "1"

• 'B' → "2"

• ...

• 'Z' → "26"

Given a string s containing only digits, return the number of ways to decode it.

Example: 

s = "226"

answer is 3 (decodings are "BZ", "VF", "BBF").

1. Clarify Requirements Before Jumping Into Code

First, let's restate the problem in our own words and ask the kinds of questions that could affect our approach.

Input: a string of digits.

Output: an integer - the number of valid decodings.

Details to clarify:

• Can the string contain non-digit characters? Assume no, only digits 0–9.

• Can the string be empty? Yes, and we should agree on what to return. Most versions say 0.

• Is a leading zero valid? No, '0' can't stand alone as a letter, and no letter starts with '0'.

• Are two-digit decodings always allowed? Only if they fall between 10 and 26 inclusive.

• Do we return the count or the actual decoded strings? Just the count.

The thing to flag here is that '0' is going to be a recurring problem. It can't be decoded by itself, but "10" and "20" are perfectly valid. We'll need to handle that carefully.

2. Identify the Category of the Question

A few signals jump out:

• We're counting the number of ways to do something, not finding an optimum.

• The decisions are local - at each position, we either consume one digit or two.

• The choices overlap heavily across different decodings (the suffix after position i is the same regardless of how we got to i).

This combination - counting, local choices, overlapping subproblems - points to dynamic programming. Specifically, this is a 1D DP over the string's length, in the same family as Climbing Stairs and House Robber.

3. Brute Force Solution

As always, we start with the brute force. The most direct approach is a recursion where we try every possible split: at each position, decode one digit if it's valid, decode two digits if they form a number between 10 and 26, and sum the counts.

decode(i):
    if i == n: return 1   # reached the end, one valid decoding
    count = 0
    if s[i] is valid single digit (not '0'):
        count += decode(i + 1)
    if s[i..i+1] is valid two-digit number (10–26):
        count += decode(i + 2)
    return count

The time complexity here is exponential, O(2^n), because at each index we potentially branch in two directions. It's conceptually clean, but won't scale.

The brute force does teach us one thing worth carrying forward: the count at each index depends only on the count at the next one or two indices. The work overlaps massively, which means we can collapse it with DP.

4. Brainstorm More Solutions

Let's formalize our understanding of the recursive solution and see how we can evolve it into a dynamic programming solution.

Step 1: How would we count this manually?

Let's think about how we would count decodings for "226" by hand.

Starting from the left, the first character is '2'. That's a valid single decoding (B). It's also part of a potential two-digit decoding "22" (V), which is between 10 and 26, so that's valid too. So I have two branches to explore. From "26", the same logic applies: '2' alone (B) leads to "6" (F), and "26" together (Z) leads to the empty string. Counting the leaves of that tree gives me 3.

The pattern looks like this: at each position, the number of decodings starting from there is the sum of the decodings starting one step ahead (if the single digit is valid) and two steps ahead (if the two-digit number is valid). That's the recurrence, we just need to formalize it.

Step 2: Write the recursion

Let decode(i) be the number of ways to decode the suffix of s starting at index i.

The base case is decode(n) = 1. Once we've consumed the whole string, we have one valid decoding left.

The transitions follow directly from the manual walkthrough:

• If s[i] is between '1' and '9', we can consume it as a single digit and recurse on decode(i+1).

• If s[i..i+1] forms a number between 10 and 26, we can consume it as a pair and recurse on decode(i+2).

private int decode(String s, int i) {
    if (i == s.length()) return 1;
    if (s.charAt(i) == '0') return 0;  // can't decode '0'

    int count = decode(s, i + 1);

    if (i + 1 < s.length()) {
        int twoDigit = (s.charAt(i) - '0') * 10 + 
                       (s.charAt(i + 1) - '0');
        if (twoDigit <= 26) {
            count += decode(s, i + 2);
        }
    }
    return count;
}

As we already noted, this works, but it's exponential. As the recursion deepens, the same indices get recomputed over and over, and the call tree balloons toward O(2^n).

Step 3: Optimize the recursion with memoization

When looking for optimizations in recursion, we should start by thinking about where we might be repeating work. The answer here is staring us in the face - every overlapping decode(i) call returns the same value, because it's a pure function of i and the input string.

So we cache it. The first time we see a given i, we compute it and store it; every subsequent call returns the cached value in O(1). That instantly drops the runtime to O(n), because each of the n possible indices is computed exactly once.

public int numDecodings(String s) {
    Integer[] memo = new Integer[s.length()];
    return decode(s, 0, memo);
}

private int decode(String s, int i, Integer[] memo) {
    if (i == s.length()) return 1;
    if (s.charAt(i) == '0') return 0;

    // For previously solved subproblems, return the cached answer.
    if (memo[i] != null) return memo[i];

    int count = decode(s, i + 1, memo);
    if (i + 1 < s.length()) {
        int twoDigit = (s.charAt(i) - '0') * 10 + 
                       (s.charAt(i + 1) - '0');
        if (twoDigit <= 26) {
            count += decode(s, i + 2, memo);
        }
    }
    return memo[i] = count;
}

This is the easiest version to write because it's a direct translation of the recursion plus a cache. If we're short on time in an interview or worried about getting the bottom-up indexing right, this is a fine solution to land on.

Step 4: From memoization to bottom-up DP

Memoization helps, but recursion still has limitations. Recursion incurs a function call overhead, and a stack depth proportional to n that can blow up on long inputs.

To optimize further, let's think about what specific pieces of data we need at every iteration. If we imagine ourselves at position i, we see that in order to calculate decode(i) we need two pieces of data: decode(i+1) and decode(i+2). Those are states with larger indices. That means we would always have the data we need to calculate decode(i) if we were to process the string from back to front. Or, equivalently, we can just flip the state definition to use prefixes instead of suffixes and iterate forward - which is the more conventional form for 1D string DP.

Let's formalize this. Let dp[i] be the number of ways to decode the prefix s[0..i-1] - the first i characters. The answer we want is dp[n].

To compute dp[i], let's ask ourselves: what are the possible previous decoding steps?

If we we were able to decode a valid single digit in the previous iteration, then we could have previously been at dp[i-1].

Or, if we were able to decode a two-digit combination in the previous iteration, then we could have previously been at dp[i-2].

So:

dp[i] = (valid single ? dp[i-1] : 0) + (valid double ? dp[i-2] : 0)

Both transitions can fail, both can succeed, or just one can succeed. If both fail, dp[i] = 0 and the zero propagates forward, correctly returning 0 for any undecodable string.

Step 5: Base cases

Let's think about our base cases. We know that an empty string has exactly one solution, the empty decoding, so that means we can set dp[0] = 1.

Can we draw any conclusions about the first character in our input string? If it's between 1 and 9, then we have the possibility of a single digit decoding, which means we have exactly 1 solution. But we have to remember that the digit can be 0 as well, and that would not have any valid decodings. So:

• dp[0] = 1. The empty prefix has exactly one way to decode (the empty decoding).

• dp[1] = 1 if s[0] is between '1' and '9', otherwise it's 0.

And now we have all the pieces we need to build a working, bottom-up DP solution! It has a time and space complexity of O(n). This solution will likely get you through the door at most companies.

Step 6: Optimize the space

To really impress the interviewer, however, you should look to optimize your DP solution even further. Look at the recurrence: dp[i] depends only on dp[i-1] and dp[i-2]. We never look further back than two indices. That means we actually don't need a full array - two variables are enough!

int prev2 = 1;          // dp[i-2]
int prev1 = (s.charAt(0) != '0') ? 1 : 0;   // dp[i-1]
for (int i = 2; i <= n; i++) {
    int curr = 0;
    if (s.charAt(i - 1) != '0') curr += prev1;
    int twoDigit = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
    if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
}
return prev1;

Same O(n) time, but now with O(1) space.

This progression - recursion → memoization → bottom-up DP → rolling variables - isn't four separate solutions. It's one solution being refined. Each step removes a specific inefficiency: memoization removes redundant computation, bottom-up removes the recursion stack, and rolling variables remove the unused entries of the array. Showing that progression in an interview demonstrates that you understand why each optimization works, not just that it exists. It's a pattern you can count on in DP problems.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Brute-force recursion	Exponential	O(n) stack	Never, but worth mentioning to frame the problem
Recursion + memoization	O(n)	O(n)	Easiest to write if I'm short on time and the recurrence is fresh
Bottom-up DP array	O(n)	O(n)	My default interview answer - clean and easy to walk through
Rolling variables	O(n)	O(1)	If asked to optimize space, or as the natural follow-up

6. Pseudocode

n = length of s
if s is empty or s[0] == '0': return 0

dp[0] = 1
dp[1] = 1

for i from 2 to n:
    if s[i-1] is between '1' and '9':
        dp[i] += dp[i-1]
    twoDigit = number formed by s[i-2] and s[i-1]
    if twoDigit between 10 and 26:
        dp[i] += dp[i-2]

return dp[n]

7. Edge Cases

Things to verify before claiming we're done:

• Empty string → return 0.

• String starting with '0' (e.g., "06") → dp[1] = 0 propagates to a final 0. ✓

• Zeros in the middle that form a valid pair (e.g., "10", "20") → handled by the two-digit transition. ✓

• Zeros that don't form a valid pair (e.g., "30", "100") → both transitions fail, dp[i] = 0. ✓

• Single-character strings → handled by dp[1] base case.

• All valid pairs (e.g., "1212") → recurrence accumulates correctly.

The cases that break naive solutions all involve '0'. Validating every transition before counting it is what makes those cases just work.

8. Full Code

public class DecodeWays {

    public static int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n + 1];

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            char one = s.charAt(i - 1);
            char two = s.charAt(i - 2);

            // Single-digit decode
            if (one >= '1' && one <= '9') {
                dp[i] += dp[i - 1];
            }

            // Two-digit decode
            int twoDigit = (two - '0') * 10 + (one - '0');
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}

Here's a challenge for you: What changes would you make to implement the space-optimized form of DP that we described earlier?

9. Test the Code

System.out.println(numDecodings("12"));     // 2
System.out.println(numDecodings("226"));    // 3
System.out.println(numDecodings("06"));     // 0
System.out.println(numDecodings("10"));     // 1
System.out.println(numDecodings("2101"));   // 1
System.out.println(numDecodings("27"));     // 1
System.out.println(numDecodings("100"));    // 0

These hit the meaningful cases: standard decodings, leading zeros, valid zero-pairs, invalid zero-pairs, and sequences where the two-digit pair exceeds 26.

10. Key Lessons

• When a recurrence has multiple transitions, validate each one before counting it. Decode Ways is hard not because the recurrence is complex, but because every transition has a precondition that's easy to forget.

• dp[0] = 1 for counting problems isn't a hack - it's the identity element that makes the recurrence work at the boundary. Treat it as foundational, not a special case.

• When zero (or any "neutral-looking" value) appears in your input, ask whether it really is neutral. In Decode Ways, '0' looks like a digit but behaves more like an invalidation marker.

• 1D DP problems where state depends on the previous one or two indices almost always have an O(1)-space rolling-variable form. Mention it as the follow-up after writing the cleaner array version.

  
  

Good Luck and Happy Coding!