ENIGMA03 - Editorial

PROBLEM LINK:

Cut and Paste

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];

SOLUTION

DP Solution Link

//