Author and Editorialist : Vishal Sharma
Brute force approach
Time complexity - O( |str1| * |str2| )
Result – time limit exceeded
First, check whether all characters in str2 are also present in str1. If not, it is impossible to obtain str2 using str1.
Then, write a nested loop to search each character of str2 in str1.
Dynamic programming solution
time complexity – O( |s1|*26 + |s2|)
First create a matrix l[|s1+1|]
l*[j]=first occurrence of character j in the string s1[i…|s1|-1]
if j is not present in the s1[i…|s1-1|], l*[j]=|s1|
if (s1* == j)
l*[j] = i;
else if (i + 1 < n1)
l*[j] = l[i + 1][j];