Count decodings of a digit string
Company: Morgan Stanley
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a non-empty digit string s consisting of characters '0'–'9' and a mapping where 1->'a', 2->'b', ..., 26->'z'. Return the number of valid ways to decode s. Note that '0' cannot be decoded alone and is only valid as part of '10' or '20'. Provide an O(n) time solution, explain how to handle zeros and invalid prefixes, analyze time and space complexity, and implement in C++. Optionally include a space-optimized variant.
Quick Answer: Count decodings of a digit string evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
A message containing letters A-Z is encoded to digits using the mapping 1->'a', 2->'b', ..., 26->'z'. Given a non-empty digit string `s` consisting of characters '0'-'9', return the number of valid ways to decode it back into letters.
Rules:
- A single digit '1'-'9' decodes to one letter.
- A two-digit group decodes to a letter only when its value is between 10 and 26 inclusive.
- The digit '0' cannot stand alone; it is only valid as the second digit of '10' or '20'. Any other appearance of '0' (e.g. a leading '0', or '0' preceded by a digit > 2) makes that prefix undecodable.
If the string cannot be decoded at all, return 0. Aim for O(n) time and O(1) extra space.
Constraints
- 1 <= len(s) <= 100
- s consists only of characters '0'-'9'
- Return 0 when s is undecodable (e.g. leading '0', or '0' not following '1' or '2')
Examples
Input: ("12",)
Expected Output: 2
Explanation: "12" decodes as 'ab' (1,2) or 'l' (12), giving 2 ways.
Input: ("226",)
Expected Output: 3
Explanation: "226" -> 'bbf'(2,2,6), 'vf'(22,6), 'bz'(2,26): 3 ways.
Hints
- Let dp[i] be the number of ways to decode the prefix s[0..i-1]. Each step you either consume one digit or two digits, so dp[i] depends only on dp[i-1] and dp[i-2] — a perfect fit for a rolling two-variable DP (O(1) space).
- A single digit contributes dp[i-1] only when s[i-1] != '0'. A two-digit group s[i-2..i-1] contributes dp[i-2] only when its numeric value is between 10 and 26.
- Handle '0' carefully: a leading '0' is immediately undecodable, and any '0' that is neither '10' nor '20' kills that path. If at any position the running count becomes 0, the whole string is undecodable, so return 0.