String | DP?

Given a string S, what are the minimum no of characters to be removed so that it does not contain the string T as a sub sequence?


S:- abcaht
T:- cat

answer is 1
abcah / abcht / abaht

I am not very sure but I think we can just remove all the occurrence of the lowest occurring character of T in S, like here frequency of c is 1, a is 1 and t is 1 so we can remove any of them.
Eg : s = aaabbc
t = abc
Ans : 1
We could just remove c. As it has the lowest frequency in S.
Again I am not very sure about this.

1 Like

No this won’t work. if the string is taccckfs , you dont have to remove any character…

@vai53, ooh yeah…

1 Like

Of course you first have to check weather original string contains string T as a subsequence or not if it doesn’t then answer is 0, otherwise @sumit_king method works I guess.

it would not work. For eg :
S = abaaacccb
T = abc
Then the answer would be just 1, if we remove the second element(b). My above approach would not work here

1 Like

Someone pls answer this…