Skip to main content

65. Decode Ways

mediumAsked at Plaid

Count the number of ways to decode a digit string where 'A'=1 ... 'Z'=26. Plaid asks this as a DP warm-up before harder parser-state problems on variable-length transaction-code formats.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid DP intro.

Problem

A message containing letters from A-Z can be encoded into numbers using the mapping 'A' -> '1', 'B' -> '2', ..., 'Z' -> '26'. Given a string s containing only digits, return the number of ways to decode it.

Constraints

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

Examples

Example 1

Input
s = "12"
Output
2

Explanation: 'AB' (1,2) or 'L' (12).

Example 2

Input
s = "226"
Output
3

Explanation: 'BZ' (2,26), 'VF' (22,6), or 'BBF' (2,2,6).

Example 3

Input
s = "06"
Output
0

Approaches

1. Recursive

Try 1-digit and 2-digit choices.

Time
O(2^n)
Space
O(n)
// Exponential without memo.

Tradeoff: TLE.

2. 1D DP

dp[i] = number of ways to decode s[0..i]. dp[i] = dp[i-1] if s[i-1] is 1-9, plus dp[i-2] if s[i-2..i-1] is 10-26.

Time
O(n)
Space
O(n) or O(1) with two variables
function numDecodings(s) {
  if (s[0] === '0') return 0;
  const n = s.length;
  let prev2 = 1, prev1 = 1;
  for (let i = 1; i < n; i++) {
    let curr = 0;
    if (s[i] !== '0') curr += prev1;
    const two = parseInt(s.slice(i - 1, i + 1), 10);
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: Linear time, O(1) space using two rolling variables. The two cases (single digit valid, two digits in 10-26) sum independently.

Plaid-specific tips

Plaid grades this on the zero-handling — '0' alone is invalid, but '10' and '20' are valid two-digit codes. Bonus signal: enumerate the edge cases explicitly before coding: leading 0, '0' anywhere, two-digit starting with 3+, etc.

Common mistakes

  • Including '00' as a valid two-digit decode — it's not (0 maps to nothing).
  • Not checking 's[i] != 0' before adding the single-digit contribution.
  • Off-by-one between dp index and string index.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Decode Ways II (LC 639) with '*' wildcards.
  • Variable-length encoding (3-digit codes too).
  • Parse and count valid IP addresses.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What's invalid about '0' alone?

There's no letter mapped to 0. So '06' has 0 decodings (you can't start with '0', and '6' alone after '0' doesn't help if you can't consume the '0').

Why two-digit check is 10-26 not 1-26?

01-09 would mean the first digit is 0, which we already disallowed. Restricting to 10-26 makes the no-leading-zero rule explicit.

Practice these live with InterviewChamp.AI

Drill Decode Ways and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →