60. Decode Ways

mediumAsked at Workday

Count the number of ways a digit string can be decoded as letters A-Z (1=A, 26=Z). Workday uses this for DP with constraint-checking — same shape as counting valid time-zone codes from a raw integer stream.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

Glassdoor (2025)— Workday SDE2 phone screen.

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> '1', 'B' -> '2', ..., 'Z' -> '26'. To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). 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

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

Example 2

Input

s = "226"

Output

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

Example 3

Input

s = "06"

Output

Approaches

1. Recursive without memo

f(i) = decode s[i] as one digit + decode s[i..i+1] as two.

Time: O(2^n)
Space: O(n)

function f(i){ if (i===s.length) return 1; if (s[i]==='0') return 0; ... }

Tradeoff: Exponential.

2. DP with two rolling variables

prev2 = ways ending at i-2; prev1 = ways ending at i-1. New = (s[i] != 0 ? prev1 : 0) + (10 <= s[i-1..i] <= 26 ? prev2 : 0).

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

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

Tradeoff: O(1) space. Note 'two >= 10' guard — '06' is not a valid two-digit decode.

Workday-specific tips

Workday loves the leading-zero edge case. '0' alone returns 0. '10' returns 1 (just 'J'). '06' returns 0 (no valid decoding). Walk through these explicitly before coding.

Common mistakes

Allowing '06' as a valid two-digit (it's < 10, not a real two-digit number).
Skipping the s[0] === '0' guard — should return 0 immediately.
Forgetting to check s[i] === '0' for the one-digit case.

Follow-up questions

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

Decode Ways II (LC 639) — with wildcards.
Count the number of distinct decodings.
What if digits can be > 9?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why 'two >= 10' not 'two >= 1'?

Two-digit numbers start at 10. '06' represents the two-character pair '0' + '6' — but '0' alone has no letter mapping, so it's not a valid two-digit decoding.

What about '0' alone?

Returns 0 — no valid decoding because letters start at A=1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →