DP 32. Distinct Subsequences | 1D Array Optimisation Technique

This chapter covers the classic Distinct Subsequences problem (LeetCode Hard), exploring string-matching dynamics within dynamic programming. We will evolve the solution from a brute-force recursive approach to memoization, tabulation, 2D space optimization, and finally a highly optimized 1D array space-saving technique.

1. Why Do We Need This? (Problem Statement & Status Quo)

We are given two strings, say S1 and S2. Our goal is to calculate how many distinct subsequences of string S1 equal string S2.

Example Walkthrough

• String S1: "babgbag"
• String S2: "bag"

If we track matching characters:

1. b (index 0), a (index 1), g (index 3) $\rightarrow$ matches "bag"
2. b (index 0), a (index 1), g (index 6) $\rightarrow$ matches "bag"
3. b (index 0), a (index 4), g (index 6) $\rightarrow$ matches "bag"
4. b (index 5), a (index 4), g (index 3) $\rightarrow$ matches "bag" (wait, let's verify indices)
5. Total valid distinct occurrences sum up to 5.

Unlike simple character-by-character greedy matching or standard Longest Common Subsequence (LCS) problems, here we must account for every possible way to match the characters of S2 inside S1. Because multiple choices exist for matching identical characters (e.g., choosing between multiple 'g's or 'b's), greedy fails, and exhaustive exploration is required.

2. Core Mental Model & The Recursive Exploration

Whenever a problem asks us to count the total number of ways to achieve a condition through choices, our instinct should jump to recursion.

The Recursive Rule for Counting Ways

1. Base cases typically return 1 (if a valid match is found/exhausted successfully) or 0 (if constraints fail).
2. We branch out across all valid choices.
3. We sum up the results from all branches and return the total accumulation.

Defining Our Parameters (I, J)

Since we have two strings (S1 and S2), we use two pointers:

• i: Represents the current index we are evaluating in string S1 (from 0 to n-1).
• j: Represents the current index we are evaluating in string S2 (from 0 to m-1).

Let f(i, j) signify: The number of distinct subsequences of string S2 (from index 0 to j) that appear in string S1 (from index 0 to i).

3. Formulating the Recurrence Relations

When comparing characters at pointers S1[i] and S2[j], two primary scenarios arise:

Case A: Characters Match (S1[i] == S2[j])

If the characters match, we have two choices:

1. Match them and move both pointers: We consume both characters and search for the remaining substring: f(i - 1, j - 1).
2. Ignore this match in S1 and search further: We might want to match S2[j] with an identical character occurring earlier in S1. Thus, we keep S2 as it is (j), but decrement S1's pointer: f(i - 1, j).

Since we need all distinct ways, we sum both choices:

Case B: Characters Do NOT Match (S1[i] != S2[j])

If they do not match, we cannot pair them. We have only one option: ignore the character in S1 and keep looking for S2[j] in the remaining prefix of S1:

4. Establishing Base Cases

When do recursive calls terminate? We track indices moving downwards from n-1 and m-1 toward -1.

1. If j < 0: We have successfully matched all characters of string S2! This counts as a valid sequence. Return 1.
2. If i < 0: We have exhausted string S1, but characters in string S2 are still left unmatched. This path is invalid. Return 0.

Summary of Base Cases & Transitions

5. Moving to Memoization (Top-Down DP)

A raw recursive solution explores branches exponentially ($\mathcal{O}(2^{N+M})$), leading to Time Limit Exceeded (TLE) due to massive overlapping subproblems.

We introduce a 2D memoization table DP[i][j] initialized to -1 to cache states.

Memoized Code Structure (C++)

long long f(int i, int j, string &s, string &t, vector<vector<long long>> &dp) {
    // Base Cases
    if (j < 0) return 1;
    if (i < 0) return 0;
    
    // Check Memo
    if (dp[i][j] != -1) return dp[i][j];
    
    // Transitions
    if (s[i] == t[j]) {
        return dp[i][j] = f(i - 1, j - 1, s, t, dp) + f(i - 1, j, s, t, dp);
    } else {
        return dp[i][j] = f(i - 1, j, s, t, dp);
    }
}

• Time Complexity: $\mathcal{O}(N \times M)$ because there are $N \times M$ unique states.
• Space Complexity: $\mathcal{O}(N \times M)$ for the DP table + $\mathcal{O}(N + M)$ for the recursion stack space.

6. Bottom-Up Tabulation (Iterative Approach)

To eliminate stack overflow and auxiliary stack space, we convert top-down recursion into a bottom-up iterative table.

Shift to 1-Based Indexing

To cleanly handle negative index base cases (-1), we shift indices by +1:

• i ranges from 1 to N (instead of 0 to N-1).
• j ranges from 1 to M (instead of 0 to M-1).
• Base case j < 0 translates to column 0, and base case i < 0 translates to row 0.

Tabulation Base Cases Setup

• When j = 0 (string S2 is empty), there is exactly 1 way to form an empty subsequence: DP[i][0] = 1 for all i.
• When i = 0 and j > 0 (string S1 is empty, but S2 is not), 0 ways are possible: DP[0][j] = 0.

Tabulation Code Implementation

int numDistinct(string s, string t) {
    int n = s.size();
    int m = t.size();
    
    // DP table with 1-based indexing
    vector<vector<double>> dp(n + 1, vector<double>(m + 1, 0));
    
    // Base Case: when S2 is empty (j = 0), there is 1 way
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return (int)dp[n][m];
}

Note: We use double (or long long with careful casting) during competitive programming implementations to prevent integer overflow issues on strict test cases where counts grow exceptionally large.

7. Space Optimization: From 2D Array to 1D Array

Looking closely at our state transition:

We do not need the entire 2D grid. We only need:

1. Previous row values
2. Current row values

This drops our space complexity from $\mathcal{O}(N \times M)$ down to $\mathcal{O}(M)$ using a single 1D array.

Crucial Traversing Direction Rule (Right-to-Left)

When optimizing to a single 1D array (prev), if we update values from left to right (1 to M), we overwrite values needed by subsequent computations in the same row. Therefore, we must iterate j backwards from M down to 1.

Final 1D Space-Optimized Code

int numDistinct(string s, string t) {
    int n = s.size();
    int m = t.size();
    
    vector<double> prev(m + 1, 0);
    
    // Base Case: Empty S2 can always be matched once
    prev[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        // Traverse backwards to prevent overwriting needed values from the previous state
        for (int j = m; j >= 1; j--) {
            if (s[i - 1] == t[j - 1]) {
                prev[j] = prev[j - 1] + prev[j];
            }
            // If they don't match, prev[j] remains unchanged (equivalent to prev[j] = prev[j])
        }
    }
    
    return (int)prev[m];
}

Summary and Key Takeaways

• Problem Nature: Counting distinct subsequences belongs to the DP on Strings family, resembling string matching with multiple branching paths.
• Why Greedy Fails: Multiple choices exist for matching duplicate characters across strings, necessitating exhaustive exploration via recursion.
• Recursive State Definition: f(i, j) tracks the count of distinct subsequences of S2 (from 0 to j) present in S1 (from 0 to i).
• Matching Transitions:
  • If characters match: Sum choices of consuming both (f(i-1, j-1)) and skipping the character in S1 (f(i-1, j)).
  • If characters mismatch: Only skip the character in S1 (f(i-1, j)).
• Base Cases: Exhausting S2 (j < 0) returns 1, while exhausting S1 (i < 0) returns 0.
• Space Optimization Evolution: We transitioned successfully from exponential recursion $\rightarrow$ Memoization $\rightarrow$ 2D Tabulation $\rightarrow$ 2-Row Optimization $\rightarrow$ 1-dimensional array optimization running in $\mathcal{O}(M)$ space by iterating backwards.