Count decodings of a digit string

Q: Count decodings of a digit string

This is a Coding & Algorithms interview question from Morgan Stanley for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Count decodings of a digit string

Comments (0)