Approaches To Problem Solving #16(DP| Subsequences)
Problem: Given the strings “A” and “B” consisting of lowercase alphabet characters, return the number of subsequences of “A” that are equal to “B”. Mod the result by 10**9 + 7.
Let us consider an example to understand the problem better,
We can explain the above example as follows,
In majority of the cases when we are dealing with problems in which we have to return the number of ways of doing something and the total number of ways can be really large, it is better to memoize our solutions for some states so that we can refer to the solutions of the sub-problems for finding solution for a given problem.
Let us dive into a recursive solution that involves memoization as well,
Approach #1 : Let us break our problem into States, Transistions and Base Cases. Initially, we define our states using two iterators, one to traverse the first string and the other for traversing the other. We can have more variables to define our states later, if we need them.
Let us try to define our transitions. Assuming the first string be “A” and the other one be “B”, if the indices for the current state points to the same character in both A and B, then we have two options either we increment both the iterators by 1 for checking the next character in B, or explore the next possibilities for this character in B by just incrementing the iterator pointing to string A by 1. In the case when the characters defined by the current states don’t point to the same character in both the strings, we increment the iterator pointing to string A by 1. There cannot be any other case and hence the above transitions seem sufficient.
Talking about the base cases, there can be two possibilities, either we run out of bounds for the first string, or we run out of bounds for the other string. In the first case, if we are out of bounds for the string B too, we add 1 to our number of ways. Considering the case when we only run out of bounds for string B, we know that we have found some subsequence in A that equals B, hence we add 1 to our number of ways.
Defining our transitions mathematically,
dp[indA][indB] = rec(indA + 1, indB)
if(A[indA] == B[indB]):
dp[indA][indB] += rec(indA + 1, indB + 1)
where ‘dp’ array is used for memoization, and ‘rec’ is the recursive function.
Not to forget that we keep the account of the result Mod 10⁹ + 7.
The time complexity for this solution is O(N * M), where N is the size of string A and M is the size of string B.
In our next article, one of the problems that we are going to discuss is given below,
Problem: Given a binary tree, return the longest path that alternates, going down from one child to the other child. For example, it may alternate between right child, left child, right child, etc. Or left child, right child, left child, etc, going down.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Dynamic Programming, String and Subsequences further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
This is the 16th article of the “Approaches To Problem Solving” series.
More such posts can be found at :-
