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?
example:-
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…
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
Similar to this question?