MediumDynamic ProgrammingStringUpdated Sep 2026

91. Decode Ways

Asked at Google, Meta, Amazon, Microsoft and 4 more

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Dynamic Programming

Companies

8

Problem

A secret message is encoded as a string of digits. Each letter maps to a number: 'A' is 1, 'B' is 2, and so on up to 'Z' which is 26. To read the message back, you cut the digit string into pieces, and each piece must be a number from 1 to 26.

Because some codes fit inside others, one string can be cut in several ways. For example "25" can be read as "2" then "5" (letters B and E), or as the single code "25" (letter Y).

Given the digit string s, return how many different valid ways it can be split into codes. A piece may not start with 0: "6" is fine, but "06" is not a valid code. If no valid split exists at all, return 0.

One string, several valid cuts

s"2""2""6"226012Cut 1: 2 | 2 | 6 gives the letters B, B, Fs"22""6"226012Cut 2: 22 | 6 gives the letters V, Fs"2""26"226012Cut 3: 2 | 26 gives the letters B, Z — three cuts intotal
Each piece must be a code from 1 to 26, and no piece may start with 0.

Constraints

  • ●1 <= s.length <= 100
  • ●s contains only digits
  • ●s may contain leading zeros
  • ●The answer fits in a 32-bit integer

Examples

Example 1
Inputs = "12"
Output2
WhyWe can cut it as "1" + "2" (A, B) or as the single code "12" (L). Both are valid, so there are 2 ways.
Example 2
Inputs = "226"
Output3
WhyThe valid cuts are 2|2|6 (BBF), 22|6 (VF) and 2|26 (BZ). That is 3 ways.
Example 3
Inputs = "06"
Output0
WhyThe first piece would be "0", which is not a code, and "06" is not a code either because of the leading zero. So there is no valid split.

Asked At

8 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
UberMediumView all Uber questions →
WalmartMediumView all Walmart questions →
AndurilMediumView all Anduril questions →

How to Think About It

1

Similar to climbing stairs: at each position, you can take 1 digit or 2 digits (if valid). The difference is that not all choices are valid.

2

dp[i] = dp[i-1] (if single digit s[i-1] is valid, i.e., not 0) + dp[i-2] (if two digits s[i-2:i] form 10-26).

3

A single digit is valid if it's 1-9 (not 0). A two-digit number is valid if it's 10-26 (not 00, 01-09, 27-99).

4

Space optimization: use two variables instead of an array, same as climbing stairs.

5

Edge cases: leading zeros (return 0), single digit (1 if valid), digits > 26 at the end.

Optimal Approach

Step 1: If s is empty or starts with 0, return 0.
Step 2: Initialize prev2 = 1, prev1 = 1.
Step 3: For i from 1 to len(s)-1:
curr = 0
If s[i] != '0': curr += prev1 (single digit valid)
If 10 <= int(s[i-1:i+1]) <= 26: curr += prev2 (two digits valid)
prev2, prev1 = prev1, curr
Step 4: Return prev1.

Time: O(n). Space: O(1).

Counting ways with two running values

s226012i=0Start: prev2 = 1, prev1 = 1 (the empty prefix has oneway)s226012i=1i=1: single "2" is valid (+1), "22" is 10-26 (+1), socurr = 2s226012i=2i=2: single "6" is valid (+2), "26" is 10-26 (+1), socurr = 3curr = (s[i] != '0' ? prev1 : 0) + (10 <= two digits <= 26 ? prev2 : 0)answer = prev1 = 3
At each position we add the ways from taking one digit and the ways from taking two digits.
ComplexityTime O(n)Space O(1)We scan the string once, and each step only needs the two previous counts, so we keep two variables instead of a full table.

What Trips People Up in Real Interviews

1

Confusing this with "count distinct substrings." This is about counting valid decodings, not substrings.

2

Not handling zeros correctly. A single 0 is invalid (can't decode). A 0 after a 1 or 2 is valid (10 or 20), but a 0 after anything else is invalid.

3

Forgetting that two-digit numbers must be 10-26. Numbers like 27-99 can't be decoded as two digits.

4

Not handling the edge case of an empty string. Return 0, not 1.

5

Using an O(n) dp array when O(1) space with two variables is possible. Each position only depends on the previous two values — optimize space with two variables.

Solution Code

O(n) time
def numDecodings(s):
    if not s or s[0] == '0':
        return 0
    prev2, prev1 = 1, 1
    for i in range(1, len(s)):
        curr = 0
        if s[i] != '0':
            curr += prev1
        if 10 <= int(s[i-1:i+1]) <= 26:
            curr += prev2
        prev2, prev1 = prev1, curr
    return prev1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Decode Ways problem?

A message consisting of letters is encoded into numbers using the mapping `A=1`, `B=2`, ..., `Z=26`. Given a string of digits s, return the number of ways to decode it.

How do you solve Decode Ways?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Decode Ways?

Decode Ways is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart, Anduril. It is a medium difficulty problem.

What are common mistakes on Decode Ways?
  • Confusing this with "count distinct substrings." This is about counting valid decodings, not substrings.
  • Not handling zeros correctly. A single 0 is invalid (can't decode). A 0 after a 1 or 2 is valid (10 or 20), but a 0 after anything else is invalid.
  • Forgetting that two-digit numbers must be 10-26. Numbers like 27-99 can't be decoded as two digits.
  • Not handling the edge case of an empty string. Return 0, not 1.
  • Using an `O(n)` dp array when `O(1)` space with two variables is possible. Each position only depends on the previous two values — optimize space with two variables.