First, we need to think about solving an easier problem, If we remove a set of indices from the string does P exist in S as a subsequence

We can binary search the K and check by solving the above problem.