JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

DPL32 Distinct Subsequences 🔥

We are given two strings S1 and S2, we want to know how many distinct subsequences of S2 are present in S1.

Again this Problem is based on the DP on String in Prevesilly Some problem we solved the Problem using the concept of the Longest Common Subsequence

Now his portion we moved on the String Matching on DP on String

Now we solved the 3 Upcomming Problems and this Problmes are based on the DP on String Matchinbg and the Problem Level is LeetCode Hard

If we Talk about this Typle of Problem then only one things Comes into the Our Mind that is Recursion becouse only the Recursion is the Only Method to Find the all the Possible Ways

Now in the Recursion Portion we Discuss Lecture 6 and Lecture 7 we learned how to the count all the possible Ways

This is the Frame of the Recursion that we used in the Recursion Portion

Recursice Approch

Steps to form the Recursive Solution
Step 1: Express the problem in terms of indexes.

We are given two strings. We can represent them with the help of two indexes i and j. Initially, i=n-1 and j=m-1, where n and m are lengths of strings S1 and S2. Initially, we will call f(n-1,j-1), which means the count of all subsequences of string S2[0…m-1] in string S1[0…n-1]. We can generalize it as follows:

Step 2: Try out all possible choices at a given index.

Now, i and j represent two characters from strings S1 and S2 respectively. We want to find distinct subsequences. There are only two options that make sense: either the characters represented matched or Not matched

Case 1: When the characters match

if(S1[i]==S2[j]) then we have 2 Different-Different Senior Occured

S1[i] == S2[j], now as the characters at i and j match, we would want to check the possibility of the remaining characters of S2 in S1 therefore we reduce the length of both the strings by 1 and call the function recursively.

VVVV Important Point
Now, if we only make the above single recursive call, we are rejecting the opportunities to find more than one subsequences because it can happen that the jth character may match with more characters in S1[0…i-1], for example where there are more occurrences of ‘g’ in S1 from which also an answer needs to be explored.

To explore all such possibilities, we make another recursive call in which we reduce the length of the S1 string by 1 but keep the S2 string the same, i.e we call f(i-1,j).

Overall we Can Say that if S1[i] == S2[j] then we have 2 Options that is to Explore the Remaining Porribilities of the occurrences of the Current J

Picked J and Not Picked J function(i-1,j-1) + function(i-1,j)

Case 2: When the characters don’t match

if(S1[i] != S2[j]), it means that we don’t have any other choice than to try the next character of S1 and match it with the current character S2.

Then Simply call the Recursion Function for the moving into the Nect char of the i and J Constant for math if any Possible Occurance of the Current j is Possible of Not, function(i-1,j)

Summarized the both Conditions

if(S1[i]==S2[j]), call f(i-1,j-1) and f(i-1,j).

if(S1[i]!=S2[j]), call f(i-1,j).

Step 3: Return the sum of choices

As we have to return the total count, we will return the sum of f(i-1,j-1) and f(i-1,j) in case 1 and simply return f(i-1,j) in case 2.

Base Cases

if j < 0, it means we have matched all characters of S2 with characters of S1, so we return 1.

if i < 0, it means we have checked all characters of S1 but we are not able to match all characters of S2, therefore we return 0.

The final pseudocode after steps 1, 2, and 3:

Time & Space Complexity

Time Complexity: O(2^N)
Reason: Exponential Time we find out the all the Possible Path
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N))

Memoization Approch

If we Observe in the recursion tree, we will observe a many number of overlapping subproblems. Therefore the recursive solution can be memoized for to reduce the time complexity.

Steps to convert Recursive code to memoization solution:

Create a dp array of size [n][m]. The size of S1 and S2 are n and m respectively, so the variable i will always lie between ‘0’ and ‘n-1’ and the variable j between ‘0’ and ‘m-1’.

We initialize the dp array to -1.

Whenever we want to find the answer to particular parameters (say f(i,j)), we first check whether the answer is already calculated using the dp array(i.e dp[i][j]!= -1 ). If yes, simply return the value from the dp array.

If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.

Time & Space Complexity

Time Complexity:O(N*M)
Reason: There are N*M states therefore at max ‘N*M’ new problems will be solved.
Space Complexity: O(N*M) + O(N+M)
Reason: We are using a recursion stack space(O(N+M)) and a 2D array ( O(N*M)).

Tabulation Approch

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want and Memoization is the Top-down Approch.

In Tabulation Approch We Just Creat a DP Array Same as Memoization and Simply Convert the Recurance Relation into the form of the Looping

Steps to convert Recursive Solution to Tabulation one.

In the recursive logic, we set the base case too if( i < 0 ) and if( j < 0 ) but we can’t set the dp array’s index to -1. Therefore a hack for this issue is to shift every index by 1 towards the right.

To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can initialize it as 0.

First, we need to initialize the base conditions of the recursive solution.

if J == 0 that means we search all the String of the S2 in S1 So we Marked Every j == 0 is 1

if i == 0 that means we something remaining that not found in the S1 So we Marked Every i == 0 is 0

Similarly, we will implement the recursive code by keeping in mind the shifting of indexes, therefore S1[i] will be converted to S1[i-1]. Same for S2.

At last, we will print dp[N][M] as our answer.

Time & Space Complexity

Time Complexity: O(N*M)
Reason:There are 2 nested loops
Space Complexity: O(N*M)
Reason: We are using an external array of size ‘N*M’. Stack Space is eliminated.

Space Optimization

If we closelly Observed if any Tabulation Approch we used the Some Limited Stuff like: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] or dp[i][j] = dp[i-1][j] for the finding the our ans then definetly here Spaced Optimization is Possible in that types of Problems. Always Remember

Golden Rule

If we required only Prev row and Prev Collom then definetly we can Space Optimized

We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.

We will be space optimizing this solution using only one row.

We have 2 Different Way to Optimized this Problem

using 2 array

using 1 array

Same like the 0/1 and unbounded Knapsack Problem

If we clearly see the values required: dp[i-1][j-1] and dp[i-1][j], we can say that if we are at a column j, we will only require the values shown in the grey box from the previous row and other values will be from the cur row itself. So why do we need to store an entire array for it?

If we need only two values from the prev row, there is no need to store an entire row. We can work a bit smarter.

We can use the cur row itself to store the required value in the following way:

We take a single row ‘prev’.

We initialize it to the base condition.

Whenever we want to compute a value of the cell prev[j], we take the already existing value (prev[j] before new computation) and prev[j-1] (if required, in case of character match).

We perform the above step on all the indexes.

So we see how we can space optimize using a single row itself.

last our ans is prev[index2]

Time & Space Complexity

Time Complexity: O(N*W)
Reason: There are three 2 nested loops
Space Complexity: O(W)
Reason: We are using an external array of size ‘W+1’ to store only one row.