Answer: American Express OA Question 2024 May | Dynamic Programming | on-campus

Solution: Decode Ways — Space Optimized Bottom-Up DP Approach We use Dynamic Programming. Define dp[i] as the number of ways to decode the substring s[0..i-1]. At each position i, we consider: Single digit decode: If s[i-1] != '0', we can decode s[i-1] alone. Add dp[i-1]. Two digit decode: If the two-character substring s[i-2..i-1] forms a valid number between 10 and 26, add dp[i-2]. We optimize space to O(1) by only tracking the previous two DP values. Algorithm Walkthrough Initialize prev2 ...