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 2 seconds. 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](https://ideone.com/neTGqI).submission:140804991]↵
this solution works in 15ms and its memory is 176kb↵
↵
↵
If you have any solution that's different from mine can you share it with me?↵
↵
Thanks for reading :).
↵
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: [
this solution works in 15ms and its memory is 176kb↵
↵
↵
If you have any solution that's different from mine can you share it with me?↵
↵
Thanks for reading :).
