Not able to understand editorial
Not able to able to understand the precomputing part , why and how is that precomputing is done in editorial ?
Solution in editorial is O(n)
But it can be very easily done in O(nlogn)
First of all corner case is that if a character is in t but not in s then answer is -1
otherwise solution always exist
How to build the solution:
Take 26 different vectors for each lowercase character and store indices of its occuring in s in increasing order
assume your ans=1
and curind=-1;
now traverse t
for each i in t
find an index for t[i] which is strictly greater than curind
if(found){
make curind equal to that index
}
else{
ans++;
make curind equal to first index of occurance of t[i] in s
}
1 Like
I have done the same thing. For finding index use binary search. You may see this. Submission #87246971 - Codeforces
1 Like