Problem Statement

Decode Ways

Imagine a secret code where each letter is a number. 'A' is 1, 'B' is 2, all the way up to 'Z' which is 26. Someone hands you a string of digits, like "12", and asks: how many different messages could this have started as? "12" could be "AB" (the 1 and the 2 read separately) or "L" (the 1 and 2 read together as 12). So there are 2 ways. Your job is to count all the valid ways to split the digit string back into letters. One catch: there is no letter for 0, so a 0 can never stand on its own.

mediumDynamic ProgrammingDynamic ProgrammingTime: O(n) · Space: O(1)

Signals to notice

count ways to decode a digit string1-26 map to A-Zoverlapping choices

Brute force first

Recursively try decoding one or two digits at each position. Many substrings are re-decoded across different branches. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

DP: dp[i] = (ways using single digit) + (ways using two digits). If s[i] is valid (1-9), add dp[i-1]. If s[i-1.i] forms 10-26, add dp[i-2]. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `s="226"`

init: prev2=1, prev1=1 (s[0]='2' != '0')
i=1 s[1]='2': single ok +prev1=1; pair int('22')=22 in 10..26 +prev2=1 -> curr=2; shift prev2=1, prev1=2
i=2 s[2]='6': single ok +prev1=2; pair int('26')=26 in 10..26 +prev2=1 -> curr=3; shift prev2=2, prev1=3
loop ends, return prev1 = 3 ("2 26", "22 6", "2 2 6")

What must stay true

At each position, you either decode one character or two. The total decodings is the sum of both valid choices. dp[i] depends only on dp[i-1] and dp[i-2]. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

prev2, prev1 = 1, (1 if s[0] != '0' else 0)
for i from 1 to len(s)-1:
    curr = 0
    if s[i] != '0':          curr += prev1   # single digit
    if 10 <= int(s[i-1:i+1]) <= 26: curr += prev2   # pair
    prev2, prev1 = prev1, curr
return prev1

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting that '0' cannot be decoded alone — if s[i] = '0', there are zero ways from single-digit decoding. Also, leading zeros in two-digit codes (like '06') are invalid. The fix is usually to return to the meaning of each move, not just the steps themselves.

Dynamic Programming Pattern