PROBLEM LINK:Author: Michael Nematollahi PREREQUISITES:NONE PROBLEM:You're given a string consisting of characters '0' and '1'. Initially, no two '1's are adjacent. You should output the maximum number of '0's that can be flipped to '1' without having any two '1's adjacent. QUICK EXPLANATION:For each maximal substring consisting of only '0's, find out its contribution to the answer. EXPLANATION:First, let's answer the first subtask. Now let's get back to the original problem. Consider the maximal substrings of the given string that consist of only '0's. For example, if the input string is "0101000", these maximal substrings are "0", "0" and "000". It's easy to see that we can solve the problem for these substrings independently and sum the results. This solution runs in $O(N)$. Refer to the setter's solution to see the implementation. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 23 Jan, 23:51

Sir, according to what I did for case 2 where string is a combination of 0s and 1s : first counting number of '1's in the string then we can also consider suppose taking all n digits to be 0 , then applying case 1 formula i.e. n/2 or n/2 +1,, and after that subtracting the count from n/2 or n/2 + 1 that difference will be the output Is this logic wrong?? Plz reply answered 27 Jan, 23:44
