Is Distinct Subsequences easy or hard?

Distinct Subsequences is classified as a Hard problem because it requires recognizing a non-trivial dynamic programming state and handling combinatorial counting. The recurrence and space optimization often make it challenging for beginners.

Distinct Subsequences Python/Java solution

Most implementations follow the same DP recurrence across languages. Python and Java solutions typically use nested loops to fill a DP table or update a 1D array, resulting in O(m*n) runtime with optional O(n) space optimization.

How to solve Distinct Subsequences in O(n)?

The problem cannot be solved in pure O(n) time because every character of s must be compared against characters of t. However, the DP table can be compressed to O(n) space using a 1D array updated from right to left while iterating through s.

What is the best approach for Distinct Subsequences?

Dynamic programming is the standard solution. Define dp[i][j] as the number of ways the first i characters of s can form the first j characters of t. The transition either skips the current character in s or matches it with t when they are equal. This produces an O(m*n) time solution and can be optimized to O(n) space.

Is Distinct Subsequences asked at Google/Amazon/Meta?

Distinct subsequence counting problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. The question tests understanding of dynamic programming on strings, state transitions, and space optimization.

What data structure is used in Distinct Subsequences?

The core data structure is a dynamic programming array or table. The 2D version uses a matrix dp[m+1][n+1], while the optimized solution uses a single 1D array of size n+1 to store subsequence counts.

What is the time complexity of Distinct Subsequences?

The optimal dynamic programming solution runs in O(m*n) time, where m is the length of string s and n is the length of string t. Each pair of indices is processed once to compute the number of subsequence combinations.

Description Solution Video 40:15

115. Distinct Subsequences

Hard54.1% acceptance13 companies

Given two strings s and t, return the number of distinct subsequences of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
babgbag
babgbag
babgbag
babgbag