How to solve this problem?

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