How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Snapchat.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snapchat during technical interviews.

Count ways to decode digit string | Snapchat Coding Question

Q: Count ways to decode digit string

This question evaluates a candidate's skill in dynamic programming and combinatorial reasoning about string partitioning, testing competency in counting valid decodings under constraint handling and edge-case analysis.

Count ways to decode digit string

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given a string `s` consisting of digits `'0'` to `'9'`. The string encodes a message using the following mapping: - `'1'` → `A`, `'2'` → `B`, ..., `'26'` → `Z`. A **decoding** is a way to partition `s` into one or more contiguous substrings, where each substring represents a valid number between `1` and `26` (inclusive), and then map each number to its corresponding letter. Examples of valid decodings: - `"12"` can be decoded as `"AB"` (`1 2`) or `"L"` (`12`), so there are 2 ways. - `"226"` can be decoded as `"BZ"` (`2 26`), `"VF"` (`22 6`), or `"BBF"` (`2 2 6`), so there are 3 ways. Rules: - A single `'0'` is **not** a valid code. - Any two-digit number must be between `10` and `26` inclusive. - Encodings like `"06"` or `"30"` are invalid because `0` cannot start a number, and `30` is not between 10 and 26. **Task** Given `s`, return the total number of different valid decodings. **Constraints** - `1 <= len(s) <= 100` - `s` consists only of characters `'0'`–`'9'`. You may assume the result fits in a 32-bit signed integer.

Quick Answer: This question evaluates a candidate's skill in dynamic programming and combinatorial reasoning about string partitioning, testing competency in counting valid decodings under constraint handling and edge-case analysis.

You are given a string `s` consisting of digits `'0'` to `'9'`. The string encodes a message using the mapping `'1'` → `A`, `'2'` → `B`, ..., `'26'` → `Z`. A **decoding** partitions `s` into one or more contiguous substrings, where each substring is a valid number between `1` and `26` (inclusive), then maps each number to its letter. Return the total number of different valid decodings. **Rules** - A single `'0'` is not a valid code. - A two-digit number must be between `10` and `26` inclusive (so `'06'` and `'30'` are invalid). **Examples** - `"12"` → 2 (`"AB"` or `"L"`). - `"226"` → 3 (`"BZ"`, `"VF"`, `"BBF"`). - `"0"` → 0. **Constraints** - `1 <= len(s) <= 100` - `s` consists only of `'0'`–`'9'`. - The result fits in a 32-bit signed integer.

Constraints

1 <= len(s) <= 100
s consists only of characters '0'-'9'
The result fits in a 32-bit signed integer

Examples

Input: ("12",)

Expected Output: 2

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

Input: ("226",)

Expected Output: 3

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

Input: ("0",)

Expected Output: 0

Explanation: A lone '0' is not a valid code.

Input: ("06",)

Expected Output: 0

Explanation: Leading zero: '0' cannot start a number and '06' is not in [10,26].

Input: ("10",)

Expected Output: 1

Explanation: Only "J" (10); '1' '0' fails because '0' alone is invalid.

Input: ("100",)

Expected Output: 0

Explanation: The second '0' has no valid one- or two-digit decode, so the whole string fails.

Input: ("27",)

Expected Output: 1

Explanation: 27 > 26, so only the split "B" "G" (2 7) works.

Input: ("2101",)

Expected Output: 1

Explanation: Only 2 10 1 -> "BJA"; the embedded '0' forces the pairing 1 0 = 10.

Input: ("1",)

Expected Output: 1

Explanation: Single digit '1' decodes to "A".

Input: ("11106",)

Expected Output: 2

Explanation: 1 1 10 6 ("AAJF") and 11 10 6 ("KJF"); the '0' must pair with the preceding '1'.

Input: ("111111111111111111111111111111111111111111111",)

Expected Output: 1836311903

Explanation: 45 ones; the count follows the Fibonacci recurrence and reaches 1836311903, near the 32-bit signed limit.

Hints

Let dp[i] be the number of ways to decode the prefix s[:i]. The answer is dp[n].
From position i you may take one digit (valid only if s[i-1] != '0') contributing dp[i-1], or two digits (valid only if 10 <= s[i-2:i] <= 26) contributing dp[i-2].
Any '0' that cannot pair with a preceding 1 or 2 makes the whole string undecodable, so the count drops to 0.
Only dp[i-1] and dp[i-2] are needed, so two rolling variables give O(1) space.

Quick Overview

This question evaluates a candidate's skill in dynamic programming and combinatorial reasoning about string partitioning, testing competency in counting valid decodings under constraint handling and edge-case analysis.