28. Decode Ways

mediumAsked at Meta

Count ways to decode a digit string into letters — Meta's notification encoding and push-message compression pipelines use DP-based decoding to count valid parse paths through variable-length encoded payloads at scale.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

A string of digits can be decoded by mapping '1' to 'A', '2' to 'B', through '26' to 'Z'. Given a string s containing only digits, return the number of ways to decode it. If there are no valid decodings, return 0.

Constraints

1 <= s.length <= 100
s contains only digits
s may contain leading zeros

Examples

Example 1

Input

s = "12"

Output

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

Example 2

Input

s = "226"

Output

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

Approaches

1. Recursion with memoization

Recursively count decode ways from each index; memoize results to avoid recomputation of overlapping subproblems.

Time: O(n)
Space: O(n)

function numDecodings(s) {
  const memo = new Map();
  function dp(i) {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    if (memo.has(i)) return memo.get(i);
    let ways = dp(i + 1);
    if (i + 1 < s.length) {
      const two = parseInt(s.slice(i, i+2));
      if (two >= 10 && two <= 26) ways += dp(i + 2);
    }
    memo.set(i, ways);
    return ways;
  }
  return dp(0);
}

Tradeoff:

2. Bottom-up DP (space-optimized)

Compute right to left keeping only two rolling variables instead of a full dp array. O(1) space, single pass.

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

function numDecodings(s) {
  let next = 1, nextNext = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '0') { nextNext = next; next = 0; continue; }
    let cur = next;
    if (i + 1 < s.length) {
      const two = parseInt(s.slice(i, i+2));
      if (two >= 10 && two <= 26) cur += nextNext;
    }
    nextNext = next;
    next = cur;
  }
  return next;
}

Tradeoff:

Meta-specific tips

Meta interviewers use this to test DP state definition clarity. Define dp[i] precisely before coding — 'number of ways to decode the suffix starting at index i'. The '0' edge case must be handled first: a standalone '0' has no valid single-digit decode. Mention the space optimization from O(n) to O(1) as a natural follow-up to show depth.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →