The problem is this.
I guess it is a common problem. I have tried it solving with binary search.
My Approach
Python Code
Difficulty — TLE
Help Needed — I know python is slow, but there are many peoples solving it with python. My question is how this code can be optimized (especially the valid function taking O(n*k) operations)?
I have seen the editorial, using other methods. But I am learning how to implement binary search, that is why I am trying this way.
Thanks for taking the time for reading this!
UPDATE: Accepted
n <= 10^5, O(nk log n), are you serious?
To solve this problem you can check binsearch answer faster.
To simplify the solution, you can check every letter C to be k-dominated. So, you need to do binsearch 26 times (for 'a', 'b' etc.)
So, imagine that you calculated the segment [L; L+k) and calculated the amount of letters C in this segment. Then, for the next segment [L+1; L+k+1) you don't need to recalculate the answer — just check elements L and L+k. If every segment has letter C, then it is k-dominated.