Distinct Subsequences LeetCode 115

LeetCode 115 — Distinct Subsequences — gives you two strings s and t. Return the number of distinct subsequences of s which equals t. A subsequence is formed by deleting zero or more characters from s without changing the relative order of the remaining characters.

For example, if s = "rabbbit" and t = "rabbit", there are 3 distinct subsequences. Each corresponds to choosing a different one of the three b characters to skip. The problem asks you to count all such choices.

This is a classic dynamic programming problem that tests your ability to define states and transitions for string matching. The 2D DP formulation is elegant: each cell represents the number of ways to form a prefix of t from a prefix of s.

Define dp[i][j] as the number of distinct subsequences of s[0..i-1] that equal t[0..j-1]. The table has dimensions (len(s)+1) x (len(t)+1). The base case is dp[i][0] = 1 for all i, because the empty string is always a subsequence (delete everything).

For the transition, consider s[i-1] and t[j-1]. If they do not match, then s[i-1] cannot contribute to forming t[0..j-1], so dp[i][j] = dp[i-1][j] — we skip s[i-1] entirely. The count comes solely from the shorter prefix of s.

If they match, we have two choices: use s[i-1] to match t[j-1] (contributing dp[i-1][j-1] ways), or skip s[i-1] and rely on earlier characters (contributing dp[i-1][j] ways). The total is dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. This branching is what creates multiple distinct subsequences.

Let s = "rabbbit", t = "rabbit". Build a 8x7 DP table (indices 0-7 for s, 0-6 for t). Initialize the first column dp[i][0] = 1 for all i. Initialize dp[0][j] = 0 for j > 0 since an empty s cannot form a non-empty t.

Fill row by row. At dp[1][1]: s[0]=r matches t[0]=r, so dp[1][1] = dp[0][0] + dp[0][1] = 1 + 0 = 1. At dp[2][2]: s[1]=a matches t[1]=a, so dp[2][2] = dp[1][1] + dp[1][2] = 1 + 0 = 1. The interesting part comes at the three b characters.

At dp[3][3], dp[4][3], dp[5][3] (the three b positions matching t[2]=b): each accumulates from the previous, giving values 1, 1+1=2, 2+1=3 at dp[5][3]. These 3 ways propagate through the remaining characters, ultimately yielding dp[7][6] = 3.

The 2D table uses O(m*n) space where m = len(s) and n = len(t). Since each row only depends on the previous row, we can compress to a single 1D array of size n+1. However, the update order matters — we must iterate j from right to left to avoid overwriting values we still need.

Initialize dp[0] = 1 and dp[j] = 0 for j > 0. For each character s[i], iterate j from len(t) down to 1. If s[i] == t[j-1], add dp[j-1] to dp[j]. This right-to-left scan ensures dp[j-1] still holds the value from the previous row when we read it.

This 1D optimization reduces space from O(m*n) to O(n) while maintaining O(m*n) time. It is the standard interview follow-up after presenting the 2D solution. Interviewers expect you to identify and execute this optimization.

In Python, the 2D version uses a nested list dp = [[0]*(n+1) for _ in range(m+1)] with dp[i][0] = 1. Two nested loops fill the table. The 1D version uses dp = [0]*(n+1) with dp[0] = 1 and reverses the inner loop.

In Java, use a long[][] or int[][] for the 2D table. The 1D version uses a long[] to avoid overflow during intermediate additions. Both versions follow the same transition logic: check character equality, then apply the take-or-skip formula.

Be careful with data types. While the problem guarantees the answer fits in a 32-bit integer, intermediate dp values can overflow int in Java. Using long for the DP array avoids this pitfall. In Python, arbitrary precision handles it automatically.

Time complexity is O(m * n) where m = len(s) and n = len(t). We fill each cell of the DP table exactly once, and each cell computation is O(1). The two nested loops dominate the runtime.

Space complexity is O(m * n) for the 2D version or O(n) for the 1D optimized version. The 1D version is preferred in interviews as it demonstrates space awareness without sacrificing clarity.

There is no known sub-quadratic algorithm for this problem in the general case. The O(m * n) solution is optimal for the given constraints (s and t up to length 1000). The constant factor is small — just a comparison and an addition per cell.

Distinct Subsequences belongs to the family of 2D string DP problems. Edit Distance (LeetCode 72) uses a similar table but with three transitions (insert, delete, replace). Interleaving String (LeetCode 97) checks if one string interleaves two others using a boolean DP table.

For subsequence-specific practice, try Longest Common Subsequence (LeetCode 1143), which finds the length rather than the count. Is Subsequence (LeetCode 392) is a simpler warm-up that checks existence rather than counting. These problems form a natural progression.

The take-or-skip pattern from Distinct Subsequences also appears in Target Sum (LeetCode 494) and Partition Equal Subset Sum (LeetCode 416), where you choose to include or exclude each element. Recognizing this shared structure accelerates your problem-solving across categories.