Count the Ways to Decode a Numeric Cipher
Company: Tesla
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
A substitution cipher maps each uppercase English letter to a number: `'A'` → `1`, `'B'` → `2`, …, `'Z'` → `26`. To encode a word, every letter is replaced by its number and the numbers are concatenated with **no separators**.
Because the codes have different lengths, the result can be ambiguous. For example, the word `"AB"` encodes to `"1" + "2" = "12"`, and the single letter `"L"` also encodes to `"12"`. So the encoded string `"12"` could be decoded back as either `"AB"` or `"L"`.
Given a non-empty string `s` consisting only of the digits `'0'`–`'9'`, return the number of **distinct** ways `s` can be decoded back into a string of letters.
Decoding rules:
- A group of one or two consecutive digits represents a letter only if its numeric value is in the range `[1, 26]`.
- A leading zero is never valid. A group like `"0"`, `"06"`, or `"027"` cannot be a valid one- or two-digit group. The digit `'0'` can therefore only appear as the **second** digit of the groups `"10"` or `"20"`.
- If `s` cannot be decoded at all, return `0`.
### Examples
- `s = "12"` → `2` (the decodings are `"AB"` and `"L"`)
- `s = "226"` → `3` (the decodings are `"BBF"`, `"BZ"`, and `"VF"`)
- `s = "06"` → `0` (invalid: a group cannot begin with `'0'`)
- `s = "10"` → `1` (the only decoding is `"J"`; `"1","0"` is invalid because `"0"` is not a valid group)
### Constraints
- `1 <= s.length <= 100`
- `s` contains only the digits `'0'`–`'9'`.
- It is guaranteed that the number of decodings fits in a 32-bit signed integer.
### Output
Return a single integer: the number of distinct ways `s` can be decoded.
Quick Answer: This question evaluates a candidate's ability to apply dynamic programming to string decoding problems with ambiguous digit groupings. It tests recognition of overlapping subproblems and careful handling of edge cases like leading zeros, a pattern commonly used to assess algorithmic thinking in coding interviews. The task falls under coding and algorithms, requiring practical implementation rather than purely conceptual knowledge.
A substitution cipher maps each uppercase English letter to a number: `'A'` -> `1`, `'B'` -> `2`, ..., `'Z'` -> `26`. To encode a word, every letter is replaced by its number and the numbers are concatenated with **no separators**.
Because the codes have different lengths, the result can be ambiguous. For example, `"AB"` encodes to `"1" + "2" = "12"`, and the single letter `"L"` also encodes to `"12"`, so `"12"` decodes back as either `"AB"` or `"L"`.
Given a non-empty string `s` consisting only of the digits `'0'`-`'9'`, return the number of **distinct** ways `s` can be decoded back into a string of letters.
**Decoding rules:**
- A group of one or two consecutive digits represents a letter only if its numeric value is in `[1, 26]`.
- A leading zero is never valid: `"0"`, `"06"`, `"027"` are all invalid groups. The digit `'0'` can only appear as the second digit of `"10"` or `"20"`.
- If `s` cannot be decoded at all, return `0`.
**Examples:**
- `s = "12"` -> `2` (`"AB"`, `"L"`)
- `s = "226"` -> `3` (`"BBF"`, `"BZ"`, `"VF"`)
- `s = "06"` -> `0` (group cannot begin with `'0'`)
- `s = "10"` -> `1` (only `"J"`; splitting as `"1","0"` is invalid)
Constraints
- 1 <= s.length <= 100
- s contains only the digits '0'-'9'.
- The number of decodings fits in a 32-bit signed integer.
Examples
Input: ("12",)
Expected Output: 2
Explanation: "12" splits as "1","2" -> AB or as "12" -> L, giving 2 decodings.
Input: ("226",)
Expected Output: 3
Explanation: Valid splits: 2|2|6 (BBF), 22|6 (VF), 2|26 (BZ).
Input: ("06",)
Expected Output: 0
Explanation: A group cannot begin with '0', so "06" has no valid decoding.
Input: ("10",)
Expected Output: 1
Explanation: Only "10" -> J is valid; splitting as "1","0" fails because "0" is not a valid group.
Input: ("0",)
Expected Output: 0
Explanation: A leading '0' is never a valid group, so there are no decodings.
Input: ("1",)
Expected Output: 1
Explanation: Single non-zero digit decodes exactly one way (A).
Input: ("27",)
Expected Output: 1
Explanation: 27 > 26 so the two-digit group is invalid; only 2|7 (BG) works.
Input: ("100",)
Expected Output: 0
Explanation: After 10 (J) the trailing '0' cannot form any valid group, so the whole string is undecodable.
Input: ("2101",)
Expected Output: 1
Explanation: Forced split 21|01 is impossible; only 21|0? fails, so the sole valid path is 21? No: the unique decoding is 2|10|1 -> B J A.
Input: ("11106",)
Expected Output: 2
Explanation: 1|1|10|6 (A A J F) and 11|10|6 (K J F); other splits hit an isolated '0'.
Input: ("111111111111111111111111111111111111111111111",)
Expected Output: 1836311903
Explanation: 45 ones: the count follows a Fibonacci recurrence and reaches 1836311903, just under the 32-bit signed limit.
Hints
- Let dp[i] be the number of ways to decode the prefix of length i. Every decoding of that prefix ends by consuming either the last one digit or the last two digits.
- You can add dp[i-1] when the single digit s[i-1] is non-zero, and add dp[i-2] when the two-digit number formed by s[i-2..i-1] lies in [10, 26]. Watch the '0' cases: a lone '0' contributes nothing, and any two-digit group starting with '0' is invalid.
- Only the previous two dp values are ever needed, so you can reduce the array to two rolling scalars for O(1) space.