class Solution {
    /**
    Explanation
    numDecodings(String s) — entry point.
    Calls decodeCount starting from index 0.
    decodeCount(String s, int index) — recursive helper.
        - Returns the number of ways to decode the substring starting at index.
        - Base case: index == s.length() → return 1.
        - If the current character is '0' → return 0 (invalid).
        - Try 1-digit decoding → recurse index + 1.
        - Try 2-digit decoding if 10 ≤ number ≤ 26 → recurse index + 2.
    Return total count.
    example:
    decodeCount("1012", 0)
    ├─ 1-digit: "1" → invalid → 0 ways
    ├─ 2-digit: "10" → valid → decodeCount("12", 2)
        ├─ 1-digit: "1" → decodeCount("2", 3) → 1 way
        └─ 2-digit: "12" → decodeCount("", 4) → 1 way
    Total = 0 + (1 + 1) = 2 ways
    */
    public int numDecodings(String s) {
        int n = s.length();
        return decodeCount(s, 0, n);
    }

    public int decodeCount(String s, int index, int n)
    {
        if(index == n)
            return 1;
        
        // If current digit is '0', cannot decode → 0 ways
        if(s.charAt(index) == '0')
            return 0;
        
        // Take only 1 digit
        int count = decodeCount(s, index+1, n);

        // Take 2 digits if valid (10–26)
        if(index+1 < n)
        {
            int num = Integer.parseInt(s.substring(index, index+2));
            // valid number that lies in alphabet range
            if(num >= 10 && num <=26)
            {
                count += decodeCount(s, index+2, n);
            }
        }
        return count;
    }
}