Hey coder. We begin with a new question, "Distinct Transformations". Before going any further, we suggest you go through the problem's outline.
Important Link : Problem Link, Solution Video
Hey coder. We begin with a new question, "Distinct Transformations". Before going any further, we suggest you go through the problem's outline.
Important Link : Problem Link, Solution Video
Say, the source string, s1= "aaaabbbccd". We have to convert s1 into the target string s2= "abcd".
In the figure, we see that to reduce "aaaa" into "a", we have to remove 3 "a"s from s1 which can be done in ^{4}C_{3} ways. Similarly we can convert "bbb" to "b" by removing 2 "b"s from s1 which can be done in ^{3}C_{2} ways. Also "cc" is converted to "c" in 2C_{1} ways. We don't touch "d" because it's frequency is the same in both the strings.
Hence, the total ways are ^{4}C_{3} * ^{3}C_{2} * ^{2}C_{1} *1= 4*3*2*1= 24 ways.
Let's now consider a few cases:
Ans. Clearly, there are 0 ways of doing so.
Reader, we derive some formula for finding out the number of ways by using the following examples.
Example 1: s1= "yabc" and s2= "abc"
In the above figure, to convert "yabc" into "abc", we compare the first characters of both the strings. Since, 'y' is not equal to 'a', therefore it is removed. On doing so, since s1=s2, therefore we stop.
Hence there is 1 way of getting the desired answer.
Example 2: s1= "aabc" and s2= "abc".
You already know that there are 2 ways of converting s1 into s2, either by removing 'a' at 0th index of s1 or by removing the 'a' at 1st index of s1.
Let's now make a tree for it.
Initially when we have to convert "aabc" into "abc", we compare the first characters of the 2 strings. Since they are both "a", we now have 2 choices: either to remove the "a" at the 0^{th} index from "aabc" or to keep the "a" at 0^{th} index and remove the "a" at 1st index.
If we remove the 0^{th} "a", then we get 1 way from that branch because s1=s2 now.
If we keep the 0^{th} "a", then we are required to compare the second characters of both the strings. Here, since "a" is not equal to "b", therefore, as seen in example 1, "a" is removed from "abc". Since "bc" is already equal to the target "bc", therefore we find 1 more way.
Hence, there are a total of 2 ways possible.
Using the above 2 examples, we derive the formula in below figure.
Here c1+r1 represents the source string s1 where c1 is the first character of s1 and r1= rest of the s1. Similarly, c2+r2 represents the target string s2 where c2 is the first character of s2 and r2= rest of the s2.
Using the above formula, we convert "aaabbc" into "abc".
From the above figure we find that there are 6 ways of converting s1 to s2 which are listed below.
In the figure, the dots in the strings represent the characters that have been removed.
If you want to see the construction of the tree in detail, we suggest you watch the solution video.
Reader, we want you to write the code for the above discussion.
After doing that, you can also refer to the code given below.
java; true";
O(n)
O(1) not including the space required for recursion stack
We understand this approach by taking source string s1= "aaabbc" and target string s2= "abc".
A 2D dp array is formed of dimensions (s2.length()+1) * (s1.length()+1) as shown below.
The smaller problem lies at the lower right corner of the grid (s1 and s2 are both blank) and the bigger problem lies at the upper left corner of the grid (s1="aaabc" and s2="abc").
Hence, we move from smaller to bigger problems.
For the last row of the grid, we have to convert ".", "c.", "bc.", "bbc.", "abbc.", "aabbc." and "aaabbc." into a blank string.
All of them have 1 way of doing so, by removing all the characters of the string.
Hence, the grid looks like Figure 10 till now.
Now in the empty cells in the last column, 0 will be stored because there is no way of converting a blank string into a non-empty string by removal of any character.
For the marked cell in figure 12, "c." is to be converted to "c.". Since the first characters of both the strings are matching, therefore we make 2 calls. Either the first character "c" is removed from s1 or it isn't.
If it gets removed, then our problem is to convert a blank into a blank whose solution is stored in the cell to the diagonal of the current cell i.e. 1 way.
If it doesn't get removed, then our problem is to convert "." into "c." whose answer is stored in the cell to the right i.e. 0 ways.
Hence, the total ways to be stored in the marked cell is the sum of the above 2 cases i.e. 1+0=1.
Now for the next cell, we have to convert s1="bc." into s2="c.". Here, the first characters of both the strings are not the same, therefore we have only one option, to remove the first character, 'b' from s1.
On doing that, we are left with the problem of converting "c" into "c", whose answer is given in the cell to the right i.e. 1.
Hence, 1 is the answer of this cell too.
Reader, we want you to fill the rest of the grid in the same manner as shown above.
Your final grid should look like this figure.
In case you face any problems in filling the array, you can also refer to the solution video.
Our final answer is stored in dp[0][0] cell which stores the number of ways for converting "aaabbc" into "abc". Hence, 6 is printed.
Now we are going to write the code for the dynamic programming approach. You can just refer to the code given below.
We are sure it will be clear to you as it is pretty straightforward.
java; true";
O(n^{2})
O(n^{2})
Here we conclude our discussion. We hope you were able to understand it.
If you still face any difficulties, we recommend you to watch the solution video of this problem.
We'll see you in the next question.