I want to know why my approach is not working.
Approach:
I am counting number of ones and zeros
And also keeping track of max length of the substring with consecutive ones or consecutive zeros.
Finally, if difference b/w count of ones and zeros is less than 2 that means the string already contains almost equal number of each, so no need to optimize, min of them is the answer.
If diff is greater than 1, then we have to toggle half of the larger count bits to get optimal solution.
But we are allowed to toggle at most ‘k’ bits.
so, take x = min (diff/2, k)
But if we don’t have a substring of length at least x then we can’t toggle them, so take x=min(max_sub[id], x)
max_sub contains the max length of substring of id = 0, 1
Now adding x to min (count [0], count [1]) should give the answer, right?
Please tell where I am going wrong.
Problem Link: https://www.codechef.com/problems/KBFLIP?tab=statement