Distinct Subsequences

Distinct Subsequences

What is this problem about?

The Distinct Subsequences coding problem involves two strings, s and t. You need to find the number of unique subsequences of s that are equal to t. A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Why is this asked in interviews?

This is a classic "Hard" problem asked by companies like Uber, Microsoft, and Amazon. It tests your mastery of Dynamic Programming interview patterns. It evaluations your ability to define a recurrence relation where the current state depends on whether two characters match and how many ways the pattern was matched previously. It’s a perfect example of 2D DP.

Algorithmic pattern used

This problem is solved using 2D Dynamic Programming.

1. Let dp[i][j] be the number of ways to form the prefix t[0...j-1] using characters from s[0...i-1].
2. Base Case: dp[i][0] = 1 because there is exactly one way to form an empty string from any string (by deleting everything).
3. Transitions:
   • If s[i-1] == t[j-1]: You have two choices. Either use s[i-1] to match t[j-1] (dp[i-1][j-1]) or skip s[i-1] and find t[j-1] in the previous part of s (dp[i-1][j]).
   • If s[i-1] != t[j-1]: You must skip s[i-1], so dp[i][j] = dp[i-1][j].

Example explanation

s = "babgbag", t = "bag"

1. To find "bag":
   • We find "ba" in the prefix and then find 'g'.
   • There are multiple 'b's and 'a's and 'g's.
   • For example, we can use the 'b' at index 0, 'a' at index 1, and 'g' at index 3.
   • Or the 'b' at index 0, 'a' at index 4, and 'g' at index 6. The DP table systematically counts all these valid index combinations.

Common mistakes candidates make

• Incorrect Initialization: Forgetting the base cases for empty strings.
• Confusion between Substring and Subsequence: Trying to use sliding window logic, which only works for contiguous parts.
• Memory Management: Using a full $O(N \times M)$ table when the problem can be optimized to $O(M)$ space (since each row only depends on the previous one).

Interview preparation tip

For string DP problems, always visualize the 2D grid where rows are characters of string A and columns are characters of string B. The transition logic usually depends on whether the characters at the current intersection match. Practice "Edit Distance" and "Longest Common Subsequence" to build the intuition for this pattern.