Count decodings of a digit string

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.