The ultimate guide to dynamic programming interviews. Developed by FAANG engineers, it equips you with strategic DP skills, practice with real-world questions, and patterns for efficient solutions.

Some of the toughest questions in technical interviews require dynamic programming solutions. Dynamic programming (DP) is an advanced optimization technique applied to recursive solutions. However, DP is not a one-size-fits-all technique, and it requires practice to develop the ability to identify the underlying DP patterns. With a strategic approach, coding interview prep for DP problems shouldn’t take more than a few weeks.

This course starts with an introduction to DP and thoroughly discusses five DP patterns. You’ll learn to apply each pattern to several related problems, with a visual representation of the working of the pattern, and learn to appreciate the advantages of DP solutions over naive solutions.

After completing this course, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence.

This course is also available in C++, JavaScript, and Python—with more coming soon!

Grokking Dynamic Programming Interview

# Statement

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

> **Note:** A string $X$ is a subsequence of string $Y$ if deleting some number of characters from $Y$ results in the string $X$.

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

* `str1 = "bbagbag"`
* `str2 = "bag"`

In this example, `str2` appears $7$ times in `str1` as a subsequence:

1. #color=Blue# b #color#b#color=Blue# ag #color#bag
2. #color=Blue# b #color#b#color=Blue# a #color#gba#color=Blue# g #color#
3. #color=Blue# b #color#bagb#color=Blue# ag #color#
4. b#color=Blue# bag #color#bag
5. b#color=Blue# ba #color#gba#color=Blue# g #color#
6. b#color=Blue# b #color#agb#color=Blue# ag #color#
7. bbag#color=Blue# bag #color#

**Constraints:**

* 1 $\leq$ `str1.length`, `str2.length` $\leq$ 500
* `str1.length` $\geq$ `str2.length`
* `str1` and `str2` consist of lowercase English letters

# Examples

align-center

# Try it yourself

Implement your solution in the following playground.

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;
    }
}

Help me debug only the function NumberOfSubsequences.I don't need the corrected code.I don't want explanations or code reviews. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Please don't give me the corrected code. Just provide me exact and to-the-point advice on how to correct the code so that it runs successfully on the test cases provided. 

Your current task is to review NumberOfSubsequences function And Answer the following questions: Ensure that the Longest Common Substring  pattern used? Does the code follow proper language guidelines. At the end, review the code.

Please provide a brief time complexity analysis of the function NumberOfSubsequences.While calculating time complexity, include the time complexity of built-in Java functions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function NumberOfSubsequences.While calculating space complexity, include the space complexity of built-in Java functions invoked by the code. The Answer should be to the point and in a few lines.

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = [] 
        # store the 1st expected output that should be displayed to the user 
        expected_outputs.append(self.__inputs[0] + self.__inputs[1])

        if json.dumps(self.__inputs[0] + self.__inputs[1]) == json.dumps(self.__actual_outputs[0]):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

import java.util.*;

class Main {
	static String numberOfSubsequences(String str1, String str2) {
		long t = NumSubseq.numberOfSubsequences(str1, str2);
		String ans = Long.toString(t);
		return ans;
	}
}

def sum(input_1, input_2):
    return input_1+input_2

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : "bbagbag"
    - 2 : "bag"
    output: 
    - 1 : "7"
  - name: "testcase 2"
    inputs:
    - 1: "dawawg"
    - 2: "aw"
    output:
    - 1 : "3"
  - name: "testcase 3"
    inputs:
    - 1 : "programming"
    - 2 : "ram"
    output: 
    - 1 : "4"
  - name: "testcase 4"
    inputs:
    - 1 : "googlegoogle"
    - 2 : "gogl"
    output: 
    - 1 : "14"
  - name: "testcase 5"
    inputs:
    - 1 : "ababababababababababababababababababababababababababababababababababababababababababab"
    - 2 : "abababababababababababababababab"
    output: 
    - 1 : "48402641245296107"

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : "bbagbag"
    - 2 : "bag"
    output: 
    - 1 : "7"
  - name: "testcase 2"
    inputs:
    - 1: "dawawg"
    - 2: "aw"
    output:
    - 1 : "3"
  - name: "testcase 3"
    inputs:
    - 1 : "programming"
    - 2 : "ram"
    output: 
    - 1 : "4"
  - name: "testcase 4"
    inputs:
    - 1 : "googlegoogle"
    - 2 : "gogl"
    output: 
    - 1 : "14"
  - name: "testcase 5"
    inputs:
    - 1 : "wowowl"
    - 2 : "owl"
    output: 
    - 1 : "3"

def validate_inputs(self) -> None:
        """
        self.__inputs is the list of inputs that are passed as input to function
        store the result using the self.store_result(error_msg, status)
        return : void
        """
        # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
        if self.__inputs[0] > 1000:
            self.store_result ("input 1 should be less than 1000", ValidationFunction.FAIL)
        elif self.__inputs[1] > 1000:
            self.store_result("input 2 should be less than 1000", ValidationFunction.FAIL)
        else:
            self.store_result("", ValidationFunction.PASS)


>**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 $0^{th}$ characters of `str1` and `str2`, respectively. Then, in each subsequent recursive call to the function, `i1` and `i2` are incremented based on whether or not the current characters matched, and if they did, whether we wish to count the match or not.

Given that we want to find all the subsequences of `str1` that contain `str2`, it may seem counterintuitive that we might want to ignore a match. So, let's consider a scenario where `str1` is the string "bagag" and `str2` is the string "bag". We can very quickly spot the first subsequence of `str1` that contains `str2`, that is, "#color=Blue#**bag**#color#ag", but what about the rest? Once the first two characters of `str1` have been identified as matches, unless we allow our algorithm to skip matches, it will terminate on the third character and we will miss the subsequence consisting of the first two characters of `str1` and its last character, that is, "#color=Blue#**ba**#color#ga#color=Blue#**g**#color#". Similarly, we'll miss "#color=Blue#**b**#color#ag#color=Blue#**ag**#color#". Clearly then, in order to consider all possible matching subsequences, we also need to evaluate what happens when we skip matching characters. 
 
The second thing to understand is that we will increment `i2` only when `str2[i2]` matches `str1[i1]`. The reason becomes obvious when we consider what happens in the two cases:
1. If we increment `i2`, we are effectively looking for a match for the next character of `str2` in `str1`.
2. On the other hand, if we don't increment `i2`, this means that we're still looking to match the current `str2` character against characters in `str1`.

All the time, the basic movement forward in our search is provided by the increments to `i1`.

With these three points in mind, we can set up the base cases and recursive cases of our algorithm.

* **Base cases:**
  * If we have reached the end of `str2`, that means we have found a subsequence in `str1` that contains `str2`. Therefore, we return $1$.
  * Similarly, if we have reached the end of `str1`, that means we have exhausted all the characters in `str1` before reaching the end of `str2` (else, we'd have already reached the first base case) and no subsequence containing _all_ the characters in `str2` was found. In this case, we return $0$.

* **Recursive cases:**
  * If both the characters, `str1[i1]` and `str2[i2]`, are same, we make two recursive calls to the function: 
     * One where we include the current match, that is, we increment both `i1` and `i2` by $1$.
     * The second, where we ignore the current match, that is, we only increment `i1`.
  * If the two characters, `str1[i1]` and `str2[i2]`, do not match, we only increment the `i1` pointer by $1$.

Let's implement the algorithm as discussed above:

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

Getting Started

0/1 Knapsack

Unbounded Knapsack

Recursive Numbers

Longest Common Substring

Palindromic Subsequence

Conclusion

Distinct Subsequence Pattern Matching