Distinct Subsequences - Solution & Explanation

Problem Overview: Given two strings s and t, count how many distinct subsequences of s equal t. A subsequence keeps the original order but may skip characters. The challenge is efficiently counting all valid combinations without generating them explicitly.

Approach 1: Dynamic Programming 2D Table (O(m * n) time, O(m * n) space)

This approach builds a DP table where dp[i][j] represents the number of ways the first i characters of s can form the first j characters of t. Initialize dp[i][0] = 1 because an empty target can always be formed by deleting characters from s. Iterate through both strings: if s[i-1] == t[j-1], you can either use that character (dp[i-1][j-1]) or skip it (dp[i-1][j]). Otherwise, only skipping is possible. This solution is a classic dynamic programming pattern where each state depends on previously computed prefixes.

The DP table effectively counts combinations without constructing subsequences. Each cell aggregates counts from earlier decisions, making it far more efficient than recursion or brute force enumeration.

Approach 2: Dynamic Programming with Space Optimization (O(m * n) time, O(n) space)

The 2D table can be compressed into a single array because each row only depends on the previous one. Maintain a 1D array dp[j] representing the number of ways to build the first j characters of t. Traverse the source string s, and update the DP array from right to left. Reverse iteration is critical: it prevents overwriting values that are still needed for the current iteration.

When s[i] == t[j], update dp[j+1] += dp[j]. This accumulates the number of subsequences that can extend the previous match. The algorithm still processes every pair of characters but reduces memory from O(m*n) to O(n), which matters when strings are large. This technique is common in optimized dynamic programming solutions that depend only on the previous row.

Both approaches rely heavily on prefix relationships within a string. Instead of generating subsequences, you count them using combinational state transitions.

Recommended for interviews: The 2D DP approach is the clearest explanation during interviews. It shows you understand state definition and transition logic. After that, mention the space optimization to reduce memory from O(m*n) to O(n). Interviewers often expect the optimized version for large constraints, but demonstrating the full DP table first proves you understand the underlying recurrence.