https://codeforces.com/contest/1295/problem/C

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. https://codeforces.com/contest/1295/submission/87246971

1 Like