209. Decode Ways

🔗 LeetCode Problem: 91. Decode Ways
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, String, 1D DP

Problem Statement

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2
Explanation: 
  "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: 
  "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"
Output: 0
Explanation: 
  "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Constraints: - 1 <= s.length <= 100 - s contains only digits and may contain leading zero(s).

---

🌳 Visual Understanding - The Decode Problem

The Problem We're Solving:

Encoding: Letters → Numbers
  'A' = 1, 'B' = 2, ..., 'Z' = 26

Decoding: Numbers → Letters (reverse mapping)
  "1" → 'A', "2" → 'B', ..., "26" → 'Z'

Given: Encoded string (numbers only)
Goal: Count how many DIFFERENT ways to decode it

Valid decodings:
  - Single digit: 1-9 (not 0!)
  - Two digits: 10-26 (not 27+, not 00-09!)

Understanding Valid Groupings:

String: "12"

Way 1: Group as (1)(2)
  "1" → 'A'
  "2" → 'B'
  Result: "AB" ✓

Way 2: Group as (12)
  "12" → 'L'
  Result: "L" ✓

Total: 2 ways

More Complex Example:

String: "226"

Way 1: Group as (2)(2)(6)
  "2" → 'B'
  "2" → 'B'
  "6" → 'F'
  Result: "BBF" ✓

Way 2: Group as (2)(26)
  "2" → 'B'
  "26" → 'Z'
  Result: "BZ" ✓

Way 3: Group as (22)(6)
  "22" → 'V'
  "6" → 'F'
  Result: "VF" ✓

Total: 3 ways

Why Leading Zeros Break Decoding:

String: "06"

Try: Group as (0)(6)
  "0" → ??? (no letter maps to 0) ❌

Try: Group as (06)
  "06" → ??? (not same as "6", no letter maps to 06) ❌

Total: 0 ways (cannot decode!)

Rule: '0' can ONLY appear as part of "10" or "20"
      Never alone, never as leading digit of two-digit code

Decision Tree for "226":

                    "226"
                     │
        ┌────────────┼────────────┐
        │                         │
     Take "2"                 Take "22"
     (valid)                  (valid)
        │                         │
        ↓                         ↓
      "26"                       "6"
        │                         │
   ┌────┴────┐                   │
   │         │                   │
Take "2"  Take "26"           Take "6"
(valid)   (valid)             (valid)
   │         │                   │
   ↓         ↓                   ↓
  "6"       ""                  ""
   │      (1 way)             (1 way)
   │         
Take "6"      
(valid)       
   │          
   ↓          
  ""
(1 way)

Total ways: 1 + 1 + 1 = 3 ✓

---

🧠 The AHA Moment - Why Dynamic Programming?

Key Observation:

To count ways to decode string s[0..n-1]:

  At position i, we have choices:
    1. Decode s[i] as single digit (if valid)
       → ways(i) += ways(i+1)

    2. Decode s[i..i+1] as two digits (if valid)
       → ways(i) += ways(i+2)

This is the Fibonacci-like pattern! 🎯

ways(i) = ways(i+1) + ways(i+2)  (with validity checks)

Why Not Greedy?

Greedy approach: "Always take single digit when possible"

String: "11"

Greedy:
  Take "1" → remaining "1"
  Take "1" → done
  Result: 1 way ("AA")

But optimal:
  Way 1: (1)(1) → "AA"
  Way 2: (11) → "K"
  Result: 2 ways!

Greedy misses valid groupings!
Need to explore ALL possibilities → DP! 🎯

Why Dynamic Programming?

1. OVERLAPPING SUBPROBLEMS:
   To count ways("226"):
     - Count ways("26") if we take "2"
     - Count ways("6") if we take "22"

   To count ways("26"):
     - Count ways("6") if we take "2"
     - Count ways("") if we take "26"

   Notice: ways("6") needed TWICE! ⚠️

2. OPTIMAL SUBSTRUCTURE:
   ways(i) = ways(i+1) + ways(i+2)  (with validity checks)

   Solution to position i uses solutions to i+1 and i+2
   Fibonacci-like structure!

These properties = Perfect for DP! 🎯

---

🔴 Approach 1: Brute Force (Recursion)

📐 Function Definition

Function Signature:

int numDecodings(String s)
int decodeWays(String s, int index)

What it represents:

Input Parameter s: - The encoded string (digits only) - Example: s = "226"

Input Parameter index: - Current position in string - Where we're deciding how to decode - Example: index=1 means "deciding for s[1] onwards"

Return Value (int): - Number of ways to decode from index to end - Example: decodeWays("226", 0) returns total ways to decode entire string

Purpose: - Count all valid decoding ways from current position - Try single digit and two digit decodings - Recursive exploration of all possibilities

Key Understanding:

decodeWays("226", 0) asks:
  "How many ways to decode from index 0 to end?"

At index 0 (digit '2'):
  - Option 1: Take "2" alone → count ways for remaining "26"
  - Option 2: Take "22" together → count ways for remaining "6"

Total = ways(option 1) + ways(option 2)

💡 Intuition

From current index, we have up to 2 choices:

1. Decode s[index] as single digit:
   - Must be '1'-'9' (not '0'!)
   - Count ways for s[index+1...end]

2. Decode s[index..index+1] as two digits:
   - Must be "10"-"26"
   - Count ways for s[index+2...end]

Base cases:
  - index == s.length(): Decoded entire string → 1 way
  - s[index] == '0': Invalid → 0 ways

Return: sum of valid choices

📝 Implementation

class Solution {
    public int numDecodings(String s) {
        return decodeWays(s, 0);
    }

    private int decodeWays(String s, int index) {
        // Base case: reached end of string
        if (index == s.length()) {
            return 1;  // Successfully decoded entire string
        }

        // If current digit is '0', cannot decode
        if (s.charAt(index) == '0') {
            return 0;
        }

        // Choice 1: Decode single digit
        int ways = decodeWays(s, index + 1);

        // Choice 2: Decode two digits (if valid)
        if (index + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += decodeWays(s, index + 2);
            }
        }

        return ways;
    }
}

🔍 Dry Run Example: s = "226"

decodeWays("226", 0)
├─ index=0, s[0]='2' (not '0') ✓
│
├─ Choice 1: Single digit "2"
│  └─ decodeWays("226", 1)
│     ├─ index=1, s[1]='2' (not '0') ✓
│     │
│     ├─ Choice 1: Single digit "2"
│     │  └─ decodeWays("226", 2)
│     │     ├─ index=2, s[2]='6' (not '0') ✓
│     │     │
│     │     ├─ Choice 1: Single digit "6"
│     │     │  └─ decodeWays("226", 3)
│     │     │     └─ index=3 == length → return 1 ✓
│     │     │
│     │     ├─ Choice 2: Two digits "6?" (out of bounds)
│     │     │  └─ Skip
│     │     │
│     │     └─ return 1
│     │
│     ├─ Choice 2: Two digits "26" (valid: 10-26) ✓
│     │  └─ decodeWays("226", 3)
│     │     └─ index=3 == length → return 1 ✓
│     │
│     └─ return 1 + 1 = 2
│
├─ Choice 2: Two digits "22" (valid: 10-26) ✓
│  └─ decodeWays("226", 2)
│     ├─ index=2, s[2]='6' (not '0') ✓
│     │
│     ├─ Choice 1: Single digit "6"
│     │  └─ decodeWays("226", 3)
│     │     └─ index=3 == length → return 1 ✓
│     │
│     ├─ Choice 2: Two digits "6?" (out of bounds)
│     │  └─ Skip
│     │
│     └─ return 1
│
└─ return 2 + 1 = 3 ✓

Result: 3 ways to decode "226"

NOTICE: decodeWays("226", 2) calculated TWICE! ⚠️

📊 Complexity Analysis

Time Complexity: O(2^n)

At each position, up to 2 choices
Creates binary recursion tree
Height = n (string length)
Total calls ≈ 2^n (exponential!)

For s = "1111...": Every position has 2 choices
Exponential explosion! 💥

Space Complexity: O(n)

Recursion stack depth = n (worst case)
Maximum n calls on stack at once

Why This Fails:

❌ Exponential time - too slow for length 100
❌ Recalculates same subproblems many times
❌ Times out on large inputs
✅ But shows the recursive structure!

---

🟡 Approach 2: Top-Down (Memoization)

📐 Function Definition

Function Signature:

int decodeWays(String s, int index, Integer[] memo)

What it represents:

Input Parameter s: - The encoded string - Unchanged throughout recursion

Input Parameter index: - Current position in string - Starting point for this subproblem

Input Parameter memo: - Memoization cache (array of size n+1) - memo[i] = number of ways to decode from index i to end - null = not yet calculated - Integer value = computed result

Return Value (int): - Number of ways to decode from index to end

Purpose: - Same as brute force BUT with caching - Store results to avoid recalculation - Each index calculated at most once

Key Understanding:

decodeWays("226", 1, memo) asks:
  "How many ways to decode from index 1 to end?"

First call:
  - memo[1] = null (not calculated)
  - Calculate the answer
  - Store in memo[1]
  - Return result

Second call:
  - memo[1] already has answer
  - Return immediately (no recalculation!)

💡 Intuition - The Clever Conversion

PROBLEM IDENTIFIED in Brute Force:
  Same indices checked multiple times

SOLUTION:
  Cache results the FIRST time we calculate them
  Next time → instant lookup! 🎯

HOW TO IDENTIFY WHAT TO MEMOIZE:
  1. Function parameter: index
  2. Same index always gives same answer
  3. Memoize using index as key
  4. Key range: 0 to n (inclusive, because we can reach n)

CONVERSION FROM BRUTE FORCE:
  1. Add memo array: Integer[n+1]
  2. Check cache before calculating
  3. Store result before returning
  4. Same logic, just add caching!

🎯 Base Cases Transformation

BRUTE FORCE BASE CASES:
  if (index == s.length()) return 1;
  if (s.charAt(index) == '0') return 0;

TOP-DOWN BASE CASES (SAME!):
  if (index == s.length()) return 1;
  if (s.charAt(index) == '0') return 0;

Why same?
  - Base cases define termination conditions
  - Memoization doesn't change the logic

ONLY ADDITIONS:
  1. Create memo array: Integer[n+1]
  2. Check memo[index] before calculating
  3. Store memo[index] before returning

📝 Implementation

class Solution {
    public int numDecodings(String s) {
        Integer[] memo = new Integer[s.length() + 1];
        return decodeWays(s, 0, memo);
    }

    private int decodeWays(String s, int index, Integer[] memo) {
        // Base case: reached end of string
        if (index == s.length()) {
            return 1;
        }

        // If current digit is '0', cannot decode
        if (s.charAt(index) == '0') {
            return 0;
        }

        // Check if already calculated
        if (memo[index] != null) {
            return memo[index];  // Cache HIT!
        }

        // Choice 1: Decode single digit
        int ways = decodeWays(s, index + 1, memo);

        // Choice 2: Decode two digits (if valid)
        if (index + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += decodeWays(s, index + 2, memo);
            }
        }

        // Store result before returning
        memo[index] = ways;
        return ways;
    }
}

🔍 Detailed Dry Run: s = "226"

Input: s = "226"
n = 3

Initial State:
memo = [null, null, null, null]
        ↑     ↑     ↑     ↑
        0     1     2     3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call: decodeWays("226", 0, memo)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: index=0
  Not at end (0 ≠ 3)
  s[0]='2' (not '0') ✓
  memo[0] = null → CACHE MISS

  Choice 1: Single digit "2"
    Recurse → decodeWays("226", 1, memo)

Step 2: index=1
  Not at end (1 ≠ 3)
  s[1]='2' (not '0') ✓
  memo[1] = null → CACHE MISS

  Choice 1: Single digit "2"
    Recurse → decodeWays("226", 2, memo)

Step 3: index=2
  Not at end (2 ≠ 3)
  s[2]='6' (not '0') ✓
  memo[2] = null → CACHE MISS

  Choice 1: Single digit "6"
    Recurse → decodeWays("226", 3, memo)

Step 4: index=3
  index == length (3 == 3) → BASE CASE
  Return 1

  Back to Step 3

Step 5: Back at index=2
  Got 1 from index=3
  ways = 1

  Choice 2: Two digits "6?" → out of bounds, skip

  Store: memo[2] = 1 ✓
  Return 1

  memo = [null, null, 1, null]

  Back to Step 2

Step 6: Back at index=1
  Got 1 from index=2
  ways = 1

  Choice 2: Two digits "26"
    Check: 26 valid (10-26)? YES ✓
    Recurse → decodeWays("226", 3, memo)

Step 7: index=3
  index == length → BASE CASE
  Return 1

  Back to Step 6

Step 8: Back at index=1
  Got 1 from index=3
  ways = 1 + 1 = 2

  Store: memo[1] = 2 ✓
  Return 2

  memo = [null, 2, 1, null]

  Back to Step 1

Step 9: Back at index=0
  Got 2 from index=1
  ways = 2

  Choice 2: Two digits "22"
    Check: 22 valid (10-26)? YES ✓
    Recurse → decodeWays("226", 2, memo)

Step 10: index=2
  Check memo[2] = 1 → CACHE HIT! ✨
  Return 1 immediately (no recalculation!)

  Back to Step 9

Step 11: Back at index=0
  Got 1 from index=2
  ways = 2 + 1 = 3

  Store: memo[0] = 3 ✓
  Return 3

  Final memo = [3, 2, 1, null]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 3 ways to decode "226" ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Understanding memo:
  memo[0] = 3 → "3 ways to decode from index 0 to end"
  memo[1] = 2 → "2 ways to decode from index 1 to end"
  memo[2] = 1 → "1 way to decode from index 2 to end"

Cache saved us! memo[2] used twice but calculated once!

📊 Complexity Analysis

Time Complexity: O(n)

Each index calculated at most once: O(n)
Work per index: O(1) (just addition)
Total: O(n) ✓

Massive improvement from O(2^n)! 🚀

Space Complexity: O(n)

Memoization array: O(n)
Recursion stack: O(n)
Total: O(n) + O(n) = O(n)

---

🟢 Approach 3: Bottom-Up (Tabulation)

📐 Function Definition

DP Array Definition:

int[] dp = new int[n + 1];

What dp[i] represents:

Index i: - Position in the string - Example: i=2 means "from index 2 onwards"

Value dp[i] (int): - dp[i] = Number of ways to decode from index i TO THE END - Example: dp[1] = 2 means "2 ways to decode from index 1 to end"

Purpose: - Store decode count for each position - Build from end to start (backwards) - Bottom-up: start from end, build to index 0

Key Understanding:

dp[2] = 1 means:
  "From index 2 to end, there's 1 way to decode"

dp[0] = 3 means:
  "From index 0 to end (entire string), there are 3 ways"

Building backwards ensures we know counts
for later positions before calculating earlier ones!

💡 Intuition - The Clever Conversion from Top-Down

TOP-DOWN (Recursion + Memoization):
  Start from index 0 → recurse forward → cache results

BOTTOM-UP (Iteration + Tabulation):
  Start from end → iterate backwards to index 0

  dp[n] = 1 (reached end, valid decoding)
    ↓ build backwards
  dp[n-1] = ways based on last character
    ↓ build backwards
  dp[n-2] = ways based on last two characters
    ↓ build backwards
  ...
    ↓ build backwards
  dp[0] = answer!

  Direction: END → backwards to START

WHY BACKWARDS?
  To count ways from position i:
    - Need to know ways from i+1 and i+2
    - Build from end ensures these are ready!

🎯 Base Cases Transformation - VERY IMPORTANT! 🔑

TOP-DOWN BASE CASES (in recursion):
  if (index == s.length()) return 1;
  if (s.charAt(index) == '0') return 0;

BOTTOM-UP BASE CASES (in DP table):
  dp[n] = 1;  // Reached end successfully

  For each position i from n-1 to 0:
    if (s.charAt(i) == '0') dp[i] = 0;
    else calculate based on i+1 and i+2

KEY INSIGHT - THE CLEVER THINKING:
  1. Top-down: "When do I stop recursing?"
     → At index n, return 1

  2. Bottom-up: "What's the known base case?"
     → dp[n] = 1, build backwards

  3. The '0' check becomes part of the iteration logic
     → if s[i] == '0', dp[i] = 0, otherwise calculate

🔄 Recurrence Relation

Definition:
  dp[i] = number of ways to decode from index i to end

For position i:
  - If s[i] == '0': dp[i] = 0 (invalid)
  - Otherwise:
      dp[i] = dp[i+1]  (single digit decode)

      if s[i..i+1] is "10"-"26":
        dp[i] += dp[i+2]  (two digit decode)

Formula:
  dp[i] = 0                           if s[i] == '0'
  dp[i] = dp[i+1] + dp[i+2]          if both choices valid
  dp[i] = dp[i+1]                    if only single valid

Dependencies:
  dp[i] depends on dp[i+1] and dp[i+2]

Must build BACKWARDS: n, n-1, n-2, ..., 1, 0

📝 Implementation

class Solution {
    public int numDecodings(String s) {
        int n = s.length();

        // Create DP table
        // dp[i] = number of ways to decode from index i to end
        int[] dp = new int[n + 1];

        // Base case: reached end of string
        dp[n] = 1;  // Empty string has one way (do nothing)

        // Build backwards from last character to first
        for (int i = n - 1; i >= 0; i--) {
            // If current character is '0', no way to decode
            if (s.charAt(i) == '0') {
                dp[i] = 0;
            } else {
                // Choice 1: Decode single digit
                dp[i] = dp[i + 1];

                // Choice 2: Decode two digits (if valid)
                if (i + 1 < n) {
                    int twoDigit = Integer.parseInt(s.substring(i, i + 2));
                    if (twoDigit >= 10 && twoDigit <= 26) {
                        dp[i] += dp[i + 2];
                    }
                }
            }
        }

        // Answer: number of ways to decode from start
        return dp[0];
    }
}

🔍 Detailed Dry Run: s = "226"

Input: s = "226"
n = 3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Create DP table:
dp = [0, 0, 0, 0]
      ↑  ↑  ↑  ↑
      0  1  2  3

Base case:
dp[3] = 1  (reached end, empty string)

dp = [0, 0, 0, 1]
               ↑
          base case ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Building backwards
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Iteration 1: i = 2
━━━━━━━━━━━━━━━━
s[2] = '6' (not '0') ✓

Choice 1: Single digit "6"
  dp[2] = dp[3] = 1

Choice 2: Two digits "6?" (out of bounds)
  Skip

dp[2] = 1

dp = [0, 0, 1, 1]


Iteration 2: i = 1
━━━━━━━━━━━━━━━━
s[1] = '2' (not '0') ✓

Choice 1: Single digit "2"
  dp[1] = dp[2] = 1

Choice 2: Two digits "26"
  Check: 26 valid (10-26)? YES ✓
  dp[1] += dp[3] = 1 + 1 = 2

dp[1] = 2

dp = [0, 2, 1, 1]


Iteration 3: i = 0 (FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━
s[0] = '2' (not '0') ✓

Choice 1: Single digit "2"
  dp[0] = dp[1] = 2

Choice 2: Two digits "22"
  Check: 22 valid (10-26)? YES ✓
  dp[0] += dp[2] = 2 + 1 = 3

dp[0] = 3

Final DP table:
dp = [3, 2, 1, 1]
      ↑
   ANSWER!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPLETE DP TABLE VISUALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Index:    0    1    2    3
String:  '2'  '2'  '6'  (end)
        ┌───┬───┬───┬───┐
dp[]    │ 3 │ 2 │ 1 │ 1 │
        └───┴───┴───┴───┘
         ↑             ↑
      Answer       Base case

Meaning:
  dp[0] = 3 → "3 ways to decode '226'" ✓
  dp[1] = 2 → "2 ways to decode '26'"
  dp[2] = 1 → "1 way to decode '6'"
  dp[3] = 1 → "Empty string (base case)"

Recurrence visualization:
  dp[0] = dp[1] + dp[2] = 2 + 1 = 3
  dp[1] = dp[2] + dp[3] = 1 + 1 = 2
  dp[2] = dp[3] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 3 ways to decode "226" ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

📊 Complexity Analysis

Time Complexity: O(n)

Loop from n-1 to 0: O(n)
Work per iteration: O(1)
Total: O(n) ✓

Space Complexity: O(n)

DP table of size (n+1): O(n)
No recursion stack: O(1)
Total: O(n)

---

🔵 Approach 4: Space-Optimized Bottom-Up

📐 Function Definition

Function Signature:

int numDecodings(String s)

What it represents:

Input Parameter s: - The encoded string

Return Value (int): - Number of ways to decode the string

Purpose: - Same as bottom-up BUT with O(1) space - Use only two variables instead of array - Track only dp[i+1] and dp[i+2]

Key Understanding:

Observation from bottom-up:
  dp[i] = dp[i+1] + dp[i+2]

We only need TWO previous values!
  - prev1 = dp[i+1] (one step ahead)
  - prev2 = dp[i+2] (two steps ahead)

No need for entire array! 🎯

💡 Intuition - Space Optimization

KEY INSIGHT from Bottom-Up:
  To calculate dp[i], we only need:
    - dp[i+1] (next position)
    - dp[i+2] (position after next)

  Don't need: dp[i+3], dp[i+4], ..., dp[n]

SPACE REDUCTION:
  Instead of array[n+1], use just 2 variables!

  prev2 = dp[i+2]  (two steps ahead)
  prev1 = dp[i+1]  (one step ahead)

  current = prev1 + prev2  (with validity checks)

  Then shift:
    prev2 = prev1
    prev1 = current

OPTIMIZATION:
  - No DP table needed
  - Single backwards pass
  - O(1) space! 🚀

📝 Implementation

class Solution {
    public int numDecodings(String s) {
        int n = s.length();

        // Use two variables instead of array
        int prev2 = 1;  // dp[i+2] - base case (empty string)
        int prev1 = 0;  // dp[i+1] - will be calculated

        // Special handling for last character
        if (s.charAt(n - 1) != '0') {
            prev1 = 1;
        }

        // Build backwards from second-last to first
        for (int i = n - 2; i >= 0; i--) {
            int current = 0;

            // If current character is '0', no way to decode
            if (s.charAt(i) != '0') {
                // Choice 1: Single digit
                current = prev1;

                // Choice 2: Two digits (if valid)
                int twoDigit = Integer.parseInt(s.substring(i, i + 2));
                if (twoDigit >= 10 && twoDigit <= 26) {
                    current += prev2;
                }
            }

            // Shift values for next iteration
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

🔍 Detailed Dry Run: s = "226"

Input: s = "226"
n = 3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Variables (instead of array):
prev2 = 1  (represents dp[3] - base case)
prev1 = ?  (will represent dp[2])

Handle last character s[2] = '6':
  '6' != '0' ✓
  prev1 = 1

State:
  prev2 = 1  (dp[3])
  prev1 = 1  (dp[2])

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Building backwards
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Iteration 1: i = 1
━━━━━━━━━━━━━━━━
s[1] = '2' (not '0') ✓

Calculate current (dp[1]):
  Choice 1: Single digit "2"
    current = prev1 = 1

  Choice 2: Two digits "26"
    Check: 26 valid (10-26)? YES ✓
    current += prev2 = 1 + 1 = 2

current = 2

Shift values:
  prev2 = prev1 = 1
  prev1 = current = 2

State:
  prev2 = 1  (was dp[2], now represents dp[1])
  prev1 = 2  (was dp[1], now represents dp[0] next)


Iteration 2: i = 0 (FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━
s[0] = '2' (not '0') ✓

Calculate current (dp[0]):
  Choice 1: Single digit "2"
    current = prev1 = 2

  Choice 2: Two digits "22"
    Check: 22 valid (10-26)? YES ✓
    current += prev2 = 2 + 1 = 3

current = 3

Shift values:
  prev2 = prev1 = 2
  prev1 = current = 3

Final state:
  prev1 = 3  (represents dp[0])

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
VARIABLE EVOLUTION TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step │ i  │ prev2 │ prev1 │ current │ Action
─────┼────┼───────┼───────┼─────────┼──────────────────
Init │ -  │   1   │   ?   │    -    │ Base case
Last │ 2  │   1   │   1   │    -    │ Handle s[2]='6'
  1  │ 1  │   1   │   1   │    2    │ Calculate, shift
  2  │ 0  │   1   │   2   │    3    │ Calculate, shift

Final: prev1 = 3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 3 ways to decode "226" ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Space used: Only 3 integer variables!
  - prev2
  - prev1
  - current (temporary)

Compare with bottom-up array: Would need array[4]!
Space reduction: O(n) → O(1) 🎯

📊 Complexity Analysis

Time Complexity: O(n)

Single backwards pass through string
Work per iteration: O(1)
Total: O(n) ✓

Space Complexity: O(1)

Only 3 variables used:
  - prev2
  - prev1
  - current (temporary)

No array, no recursion
Constant space! ✓

MASSIVE improvement from O(n)! 🚀

---

🎯 Pattern Recognition - Fibonacci-like DP

Core Pattern: Current = Previous + Before Previous

Template for Fibonacci-like problems:

dp[i] = dp[i+1] + dp[i+2]  (with validity checks)

Or:
dp[i] = dp[i-1] + dp[i-2]  (depending on direction)

Space optimization:
  Use two variables instead of array:
  current = prev1 + prev2

Similar Problems:
  - Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]
  - House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  - Fibonacci: dp[i] = dp[i-1] + dp[i-2]
  - Decode Ways: dp[i] = dp[i+1] + dp[i+2] (with validity)

How to Identify:

✅ Current state depends on 1-2 previous states
✅ Fibonacci-like recurrence relation
✅ Can optimize space to O(1) with two variables
✅ Linear scan with local decisions

For Decode Ways:
  ✅ dp[i] depends on dp[i+1] and dp[i+2]
  ✅ Similar to Fibonacci but with validity checks
  ✅ Can use just prev1 and prev2 variables
  ✅ One backwards pass through string

---

⚠️ Important Edge Cases to Test

// Leading zero
s = "0"              // Expected: 0
s = "06"             // Expected: 0
s = "01"             // Expected: 0

// Valid single way
s = "1"              // Expected: 1
s = "9"              // Expected: 1
s = "10"             // Expected: 1

// Multiple ways
s = "11"             // Expected: 2 ("AA" or "K")
s = "12"             // Expected: 2 ("AB" or "L")
s = "226"            // Expected: 3

// Zero in middle
s = "10"             // Expected: 1 ("J")
s = "20"             // Expected: 1 ("T")
s = "30"             // Expected: 0 (invalid)
s = "102"            // Expected: 1
s = "1201"           // Expected: 1

// Invalid two-digit
s = "27"             // Expected: 1 (only "2,7")
s = "99"             // Expected: 1 (only "9,9")

// Complex patterns
s = "111111"         // Expected: many ways
s = "123123"         // Expected: many ways

// Edge with 26
s = "26"             // Expected: 2 ("BF" or "Z")
s = "260"            // Expected: 0 (invalid)
s = "206"            // Expected: 1

// Long string
s = "1111111111"     // Expected: many ways

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Given encoded string (A→1, B→2, ..., Z→26), count ways to decode it. Must handle '0' carefully (can only appear as "10" or "20").

Function Definitions: - decodeWays(s, i) = Number of ways to decode from index i to end - dp[i] = Number of ways to decode from index i to end - Fibonacci-like: dp[i] = dp[i+1] + dp[i+2] (with validity)

Key Insight: At each position, try single digit (1-9) and two digits (10-26). Sum the ways from both choices. '0' can never be decoded alone!

Four Approaches: 1. Brute Force: Recursive exploration → O(2^n) time ❌ 2. Top-Down: Memoization → O(n) time, O(n) space ✓ 3. Bottom-Up: DP table backwards → O(n) time, O(n) space ✓ 4. Space-Optimized: Two variables → O(n) time, O(1) space ⭐

⚡ Quick Implementation

import java.util.Arrays;

public class Solution {
  public int numDecodings(String s) {
    // Approach - check decision tree in NOTES
    // decodeWays("226", 0) asks:
    // "How many ways to decode from index 0 to end?"

    // At index 0 (digit '2'):
    // - Option 1: Take "2" alone -> count ways for remaining "26"
    // - Option 2: Take "22" together -> count ways for remaining "6"

    // Total = ways(option 1) + ways(option 2)
    // Base case: index == s.length(): Decoded entire string → 1 way

    // // Approach 1 - recursive (start from index 0)
    // return recursive(0, s);

    // // Approach 2 - top down
    // int[] memo = new int[s.length()];
    // Arrays.fill(memo, -1);
    // return topDown(0, s, memo);

    // // Approach 3 - bottom up
    // return bottomUp(s);

    // Approach 4 - space optimized
    return bottomUpSO(s);
  }

  private int bottomUpSO(String s) {
    int n = s.length();

    // end of string
    int prev1 = 1; // dp[index + 1]
    int prev2 = 0; // dp[index + 2]
    int ways = 0;

    for (int index = n - 1; index >= 0; index--) {
      if (s.charAt(index) == '0') {
        ways = 0;
      } else {
        ways = prev1;
        if (index + 1 < s.length()) {
          // check if we can decode two digits at this place (index)
          int temp = Integer.parseInt(s.substring(index, index + 2));

          if (temp >= 10 && temp <= 26) {
            // decoded 2 digits
            ways = ways + prev2;
          }
        }
      }

      prev2 = prev1;
      prev1 = ways;
    }

    return ways;
  }

  private int bottomUp(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];

    // end of string
    dp[s.length()] = 1;

    for (int index = n - 1; index >= 0; index--) {
      if (s.charAt(index) == '0') {
        dp[index] = 0;

        continue;
      }

      int ways = dp[index + 1];
      if (index + 1 < s.length()) {
        // check if we can decode two digits at this place (index)
        int temp = Integer.parseInt(s.substring(index, index + 2));

        if (temp >= 10 && temp <= 26) {
          // decoded 2 digits
          ways = ways + dp[index + 2];
        }
      }

      dp[index] = ways;
    }

    return dp[0];
  }

  private int topDown(int index, String s, int[] memo) {
    // base cases
    if (index == s.length()) {
      return 1; // successfully decoded
    }

    if (index > s.length() || s.charAt(index) == '0') {
      return 0; // cannot decode
    }

    if (memo[index] != -1) {
      return memo[index];
    }

    // decoded single digit
    int ways = topDown(index + 1, s, memo);
    if (index + 1 < s.length()) {
      // check if we can decode two digits at this place (index)
      int temp = Integer.parseInt(s.substring(index, index + 2));

      if (temp >= 10 && temp <= 26) {
        // decoded 2 digits
        ways = ways + topDown(index + 2, s, memo);
      }
    }

    return memo[index] = ways;
  }

  private int recursive(int index, String s) {
    // base cases
    if (index == s.length()) {
      return 1; // successfully decoded
    }

    if (index > s.length() || s.charAt(index) == '0') {
      return 0; // cannot decode
    }

    // decoded single digit
    int ways = recursive(index + 1, s);
    if (index + 1 < s.length()) {
      // check if we can decode two digits at this place (index)
      int temp = Integer.parseInt(s.substring(index, index + 2));

      if (temp >= 10 && temp <= 26) {
        // decoded 2 digits
        ways = ways + recursive(index + 2, s);
      }
    }

    return ways;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.numDecodings("12") == 2);
    System.out.println(s.numDecodings("226") == 3);
    System.out.println(s.numDecodings("06") == 0);
    System.out.println(s.numDecodings("27") == 1);
  }
}

🔑 Key Insights

Validity Rules:

Single digit: '1'-'9' valid, '0' invalid
Two digits: "10"-"26" valid

'0' can ONLY appear as:
  - "10" (J)
  - "20" (T)

Never alone, never as leading digit of invalid code!

Examples:
  "06" → invalid (0 alone, 06 not in range)
  "30" → invalid (3 okay, but 30 > 26)
  "10" → valid (J)
  "102" → valid (J, B)

Recurrence Relation:

dp[i] = 0                           if s[i] == '0'
dp[i] = dp[i+1]                     if only single valid
dp[i] = dp[i+1] + dp[i+2]          if both valid

Why backwards?
  Need dp[i+1] and dp[i+2] to calculate dp[i]
  Build from end ensures dependencies ready!

Space Optimization:

Only need two previous values:
  prev1 = dp[i+1]
  prev2 = dp[i+2]

current = prev1 + prev2  (with checks)

Then shift:
  prev2 = prev1
  prev1 = current

Reduces O(n) space to O(1)! 🚀

🎪 Memory Aid

"Single or double, never zero alone!"
"10-26 valid, 27+ invalid!"
"Backwards build, Fibonacci-style!"
"Two variables, not array!" ✨

⚠️ Common Mistakes

• ❌ Allowing '0' to be decoded alone
• ❌ Accepting "00", "01"-"09" as valid
• ❌ Accepting "27"-"99" as valid two-digit codes
• ❌ Building DP table forwards instead of backwards
• ❌ Not handling s[i] == '0' check first
• ❌ Integer.parseInt without checking bounds

✅ Interview Talking Points

"This is a Fibonacci-like DP problem with validity constraints.

Key insight:
  - At each position, try decode 1 or 2 digits
  - Sum the ways from both valid choices
  - Critical: '0' can only be part of "10" or "20"

Bottom-Up Approach:
  1. Base: dp[n] = 1 (empty string)
  2. Build backwards from n-1 to 0
  3. For each position:
     - If '0' → dp[i] = 0 (invalid)
     - Otherwise → dp[i] = dp[i+1]
     - If two-digit "10"-"26" valid → dp[i] += dp[i+2]

Space Optimization:
  - Only need dp[i+1] and dp[i+2]
  - Use two variables: prev1, prev2
  - Reduces O(n) space to O(1)

Complexity: O(n) time, O(1) space with optimization"

---

🎉 Congratulations!

You've mastered Decode Ways - Fibonacci pattern with constraints!

What You Learned:

✅ Fibonacci-like DP - dp[i] depends on i+1 and i+2
✅ Validity Constraints - Handling '0' and range checks
✅ Backwards Building - Building from end to start
✅ String Parsing - Extracting and validating digits
✅ Space Optimization - O(n) to O(1) with two variables
✅ Edge Case Handling - Leading zeros and invalid codes

Pattern Evolution:

Problem 205: Climbing Stairs
  dp[i] = dp[i-1] + dp[i-2]
  Forward building, simple sum

Problem 209: Decode Ways
  dp[i] = dp[i+1] + dp[i+2]  (with validity)
  Backward building, conditional sum

SAME PATTERN, different direction & constraints! 🎯

The Fibonacci Family:

All use: current = prev1 + prev2

Climbing Stairs:
  - Always valid
  - Forward or backward works

Decode Ways:
  - Validity checks required
  - Backward ensures dependencies
  - '0' handling critical

House Robber (next):
  - Use MAX instead of SUM
  - Additional constraint: can't rob adjacent

Fibonacci family has many variations! 💪

You've now mastered Fibonacci-like DP with constraints! 🚀✨