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 Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Morgan Stanley.

What role is this question designed for?

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

Count decodings of a digit string | Morgan Stanley Coding Question

Quick Overview

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.

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.

Input: ("06",)

Expected Output: 0

Explanation: A leading '0' has no decoding, so the answer is 0.

Input: ("10",)

Expected Output: 1

Explanation: '0' is only valid as part of '10' here, which decodes to 'j'; exactly 1 way.

Input: ("100",)

Expected Output: 0

Explanation: After decoding '10', the trailing '0' cannot be decoded (not preceded by 1 or 2), so 0 ways.

Input: ("27",)

Expected Output: 1

Explanation: 27 > 26, so only the single-digit split 2,7 works: 'bg', 1 way.

Input: ("11106",)

Expected Output: 2

Explanation: "11106" -> 'aaj'(1,1,10,...) wait: valid splits are (1,1,10,6)->'aaj f' style and (11,10,6); '06' alone is invalid so only paths routing the '0' through '10' survive, giving 2 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.

Quick Overview