I have solved this problem but I wonder how to do this using binary search i do have one idea but i am a bit lazy to implement that because i also think that might TLE. Can you guys please help me in this. https://codeforces.net/contest/1203/problem/D2
Well, I think you can BinarySearch on the length of the subsequence that you want to remove. Then it's easy to check whether it's possible or not (it can be done in O(length(s))), you can do it like this:
int cur = 0;
int lst = -1;
bool hap = false;
for (int i = 0; i < s.size(); i++) {
if (s[i] == t[cur] && (lst == -1 || i — lst > BinarySearch-Value) && !hap) {
cur++;
lst = i;
hap = true;
}
}
if (cur == t.size() — 1) // It is possible
else // It is not possible
It won't get TLE because its time complexity is O(len(s) log len(s))
can you implement what you have written? cause i think it is wrong
:(, I just realized that it's wrong...