Distinct Subsequences - Video Solutions

Problem Overview: Given two strings s and t, count how many distinct subsequences of s equal t. A subsequence keeps character order but can skip characters. The challenge is avoiding exponential exploration while counting all valid combinations.

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

This approach builds a 2D 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 string t can always be formed by deleting characters from s. Then iterate through both strings. If s[i-1] == t[j-1], add two possibilities: use the character (dp[i-1][j-1]) or skip it (dp[i-1][j]). If they differ, only skip the character in s (dp[i-1][j]). This method explicitly models all prefix combinations, making it easy to reason about and debug. Time complexity is O(m * n) and space complexity is also O(m * n).

This is a classic example of dynamic programming applied to a string matching problem where overlapping subproblems appear when multiple subsequences reuse the same prefixes.

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

The full DP table stores many intermediate states that are only used once. Each row depends only on the previous row, so you can compress the table into a single 1D array. Maintain dp[j] as the number of ways to build the first j characters of t. Iterate through s, and update dp from right to left so previous states are not overwritten too early. When s[i-1] == t[j-1], update dp[j] += dp[j-1]. Right-to-left iteration preserves the values from the previous iteration of s. This reduces memory usage significantly while keeping the same O(m * n) runtime.

This optimization matters when the input strings are large, since the DP table can otherwise consume substantial memory. The algorithmic idea remains identical—count subsequence combinations using prefix relationships—but the storage is compressed to a single dimension.

Recommended for interviews: Interviewers usually expect the dynamic programming formulation first because it demonstrates understanding of subsequence counting and state transitions. Start by explaining the 2D DP definition (dp[i][j] meaning prefixes of s and t). Once the recurrence is clear, mention the 1D optimization to reduce space from O(m * n) to O(n). Showing both versions proves you understand both correctness and practical optimization.