You have to find the number of unique ways in which you can transform S1
to S2.
Transformation can be achieved by removing 0 or more characters from S1,
such that the sequence formed by the remaining characters of S1 is identical
to S2.
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 4C3 ways. Similarly we can convert "bbb" to "b" by removing 2
"b"s from s1 which can be done in 3C2 ways. Also "cc" is converted to "c"
in 2C1 ways. We don't touch "d" because it's frequency is the same in
both the strings.
Hence, the total ways are 4C3 * 3C2 *
2C1 *1= 4*3*2*1= 24 ways.
Let's now consider a few cases:
In how many ways can s1="abc" be converted to s2="abc" by removing 0 or more characters from
s1.
Ans. We say that there is 1 way of doing so by removing 0 ( or no) characters from s1.
In how many ways can s1="abc" be converted to s2="xyz" or s2= "abcd" by removing 0 or more
characters from s1.
Ans. Clearly, there are 0 ways of doing so.
Approach 1: Recursion Tree
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 0th index from "aabc" or to keep the "a" at 0th index and
remove the "a" at 1st index.
If we remove the 0th "a", then we get 1 way from that branch because s1=s2
now.
If we keep the 0th "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.
Code
Reader, we want you to write the code for the above discussion.
After doing that, you can also refer to the code given below.
import java.io.*;
import java.util.*;
public class Main {
public static int solution(String s, String t, int si, int ti) {
if(si==s.length()){
if(ti < t.length()){ return 0; }else{ return 1; } }else if(ti==t.length()){ return 1; } char
c1=s.charAt(si); char c2=t.charAt(ti); int tw=0; if(c1!=c2){ tw=solution(s,t,si+1,ti); }else{
int tw1=solution(s,t,si+1,ti); int tw2=solution(s,t,si+1,ti+1); tw=tw1+tw2; } return tw; }
public static void main(String[] args) { Scanner scn=new Scanner(System.in); String
s1=scn.next(); String s2=scn.next(); System.out.println(solution(s1, s2,0,0)); } }
java;
true";
Time and Space Complexity Analysis:
Time Complexity:
O(n)
Space Complexity:
O(1) not including the space required for recursion stack
Approach 2: Dynamic Programming
We understand this approach by taking source string s1= "aaabbc" and target string s2= "abc".
Storage:
A 2D dp array is formed of dimensions (s2.length()+1) * (s1.length()+1) as shown below.
Meaning:
In the figure, the marked cell stores the number of ways possible to convert source string s1=
"bbc" into the target string s2= "bc".
Direction:
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.
Solve & Traversal:
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.
Code
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.
import java.io.*;
import java.util.*;
public class Main {
public static int solution(String s, String t) {
int[][]dp=new int[t.length()+1][s.length()+1];
for(int i=dp.length-1;i>=0;i--){
for(int j=dp[0].length-1;j>=0;j--){
if(i==dp.length-1){
dp[i][j]=1;
}else if(j==dp[0].length-1){
dp[i][j]=0;
}else{
char c1=t.charAt(i);
char c2=s.charAt(j);
if(c1!=c2){
dp[i][j]=dp[i][j+1];
}else{
dp[i][j]=dp[i][j+1]+dp[i+1][j+1];
}
}
}
}
return dp[0][0];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String s1 = scn.next();
String s2 = scn.next();
System.out.println(solution(s1, s2));
}
}
java;
true";
Time and Space Complexity Analysis:
Time Complexity:
O(n2)
Space Complexity:
O(n2)
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.
