Count decodings of a digit string

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Count decodings of a digit string

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

Example 1

Input: ("12",)
Output: 2

Explanation: "12" decodes as 'ab' (1,2) or 'l' (12), giving 2 ways.

Example 2

Input: ("226",)
Output: 3

Explanation: "226" -> 'bbf'(2,2,6), 'vf'(22,6), 'bz'(2,26): 3 ways.

Hints

1. 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).
2. 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.
3. 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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Define a state that captures exactly the remaining decision information. Fill base cases first, then transition from smaller subproblems to larger ones. For games, use score difference or minimax DP; for counting, sum the valid predecessor states.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Typical DP time is number_of_states times transition_cost. Space can often be reduced when transitions only need the previous layer or diagonal.

Edge Cases and Tests

Empty input, length 1, invalid symbols, negative values where allowed, ties under optimal play, and large counts requiring modulo arithmetic.