The reason why I'm writing this blog is that the constraint of N and K is only 5000 also the time limit per test was 2seconds. Wasn't the problem supposed to be solved in like $$$O(NlogN)$$$ or $$$O(N^2)$$$.

My approach:

First, check if the answer is 1.

Second, for each char in S, I calculate the number of strings that I can generate which differs at the position $$$i$$$.

if char at $$$i$$$-th position is '1' we have to replace it with 0 and all possible solutions which we can calculate in O(1) with a preprocessing. otherwise, if $$$i$$$-th position is '0' we have to replace it with 1 and all possible solutions which we can calculate in O(1) with a preprocessing.

here is my solution: Link.

If you have any solution that's different from mine can you share it with me?

Thanks for reading :).