Decode Ways - Solution & Explanation

Problem Overview: You receive a string of digits where 1 -> A, 2 -> B, ..., 26 -> Z. The task is to count how many different ways the string can be decoded into letters. A single digit can represent one letter, while two digits can represent a letter only if the value is between 10 and 26. Handling 0 correctly is the main challenge because it cannot be decoded alone.

Approach 1: Dynamic Programming (O(n) time, O(n) space)

This problem fits classic Dynamic Programming. Each position depends on the number of ways the previous characters could be decoded. Define dp[i] as the number of ways to decode the substring ending at index i. Iterate through the string and evaluate two possibilities at each step.

First, check the single-digit decode. If s[i] is not '0', it can be decoded as a letter, so add dp[i-1]. Second, check the two-digit decode using s[i-1:i+1]. If the value falls between 10 and 26, add dp[i-2]. This builds the solution incrementally while skipping invalid combinations like "06". The base case starts with dp[0] = 1 when the first digit is valid.

This approach clearly models the decision process at every index and is easy to reason about during interviews. Time complexity is O(n) because you scan the string once, and space complexity is O(n) due to the DP array storing results for each position.

Approach 2: Optimized Space Dynamic Programming (O(n) time, O(1) space)

The DP relation only depends on the previous two states: dp[i-1] and dp[i-2]. Instead of storing the entire array, keep two variables representing those values. During iteration, compute the current number of decodings using the same rules as the full DP approach.

Check whether the current digit forms a valid single-digit decode and whether the current and previous digits form a valid two-digit number. Update the running values as you move forward through the string. This rolling-state technique removes the need for the DP array while keeping the exact same recurrence.

The algorithm still runs in O(n) time because every character is processed once, but space drops to O(1). This version is typically preferred in production-quality code or memory-constrained environments since it keeps the logic simple while minimizing memory usage.

Recommended for interviews: Start with the standard Dynamic Programming formulation because it clearly shows the recurrence relation and reasoning about valid decodings. Once the interviewer is comfortable with the logic, mention that only two previous states are needed and optimize it to constant space. Demonstrating both approaches shows strong understanding of dynamic programming transitions and optimization techniques.