Bhai ye solution appraoch kya hai?


#1

Approach samjhado koi. Mereko existential crisis aa rha hai ab…


#2

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