Grokking Dynamic Programming Interview/

...

/

Distinct Subsequence Pattern Matching

Distinct Subsequence Pattern Matching

Let's solve the Distinct Subsequence Pattern Matching problem using Dynamic Programming.

We'll cover the following...

Statement

Given two strings, str1 and str2, return the number of times str2 appears in str1 as a subsequence.

Note: A string XX is a subsequence of string YY if deleting some number of characters from YY results in the string XX.

Let’s assume that you have two strings as follows:

  • str1 = "bbagbag"
  • str2 = "bag"

In this example, str2 appears 77 times in str1 as a subsequence:

  1. bbagbag
  2. bbagbag
  3. bbagbag
  4. bbagbag
  5. bbagbag
  6. bbagbag
  7. bbagbag

Constraints:

  • 1 ≤\leq str1.length, str2.length ≤\leq 500
  • str1.length ≥\geq str2.length
  • str1 and str2 consist of lowercase English letters

Examples

No.

str1

str2

Number of Subsequences

1

"bbagbag"

"bag"

7

2

"dawawg"

"aw"

3

Try it yourself

Implement your solution in the following playground.

usercode > NumSubseq.java
import java.util.*;
public class DistinctSubsequences{
    public static int numberOfSubsequences(String str1, String str2) {
        // your code will replace the placeholder return statement below
        return -1;
    }
}
Distinct Subsequence Pattern Matching

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

The naive approach is to find all possible subsequences in str1 and check if they contain str2. For this, we make the first call to the recursive function with both the pointers, i1 and i2, pointing to the 0th0^{th} characters of str1 and str2, respectively. Then, in each subsequent recursive call to the function, i1 ...