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.

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).

Hints

  1. Let dp[i] be the number of ways to decode the prefix s[:i]. The answer is dp[n].
  2. 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].
  3. Any '0' that cannot pair with a preceding 1 or 2 makes the whole string undecodable, so the count drops to 0.
  4. Only dp[i-1] and dp[i-2] are needed, so two rolling variables give O(1) space.

Loading coding console...