Approach samjhado koi. Mereko existential crisis aa rha hai ab…
The solution uses Kadane’s Algorithm.
We have to pick that substring where there are maximum number of 0s and minimum number of 1s, i.e., substring with max(count(0)-count(1)). So that after the flip, we can get maximum number of 1s in the final string.
Iterate over the string and keep a count. Increment this count whenever we encounter a 0 and decrement it when we encounter 1. The substring which will have the maximum value of this count will be our answer.
Here’s a video by alGOds which explains the approach nicely. Do watch it if you have any doubts.
Link : https://youtu.be/cLVpE5q_-DE