Count decodings of a numeric string

Q: Count decodings of a numeric string

This question evaluates dynamic programming and string-processing skills, along with attention to edge-case handling, modular arithmetic for large results, and online algorithm design for streaming input.

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

Given a string s of digits representing an encoded message where '1' maps to 'A', ..., '26' maps to 'Z', and '0' cannot appear alone (it must be part of '10' or '20'), count the number of distinct decodings of s. Design an O(n)-time, O( 1)-extra-space algorithm. Follow-ups: handle very large n by returning the count modulo 1,000,000,007; extend the API to support streaming input where characters arrive one by one and you must update the count online.

Count decodings of a numeric string

Overview

Comments (0)