PROBLEM LINK:
Author and Editorialist : Vishal Sharma
DIFFICULTY:
Easy-Medium
PREREQUISITES:
DP
EXPLANATION:
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|][256]
l[i][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[i][j]=|s1|
if (s1[i] == j)
l[i][j] = i;
else if (i + 1 < n1)
l[i][j] = l[i + 1][j];