Minimum Number of Flips to make Binary String Alternating - Sliding Window - Leetcode 1888 - Python

0:00 - Read the problem
3:59 - Drawing Explanation
10:44 - Coding Explanation

leetcode 1888

#sliding #window #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[theghostwhowalk]

Great explanation. This should be a hard problem. Even brute force is not quite intuitive in interview setup without hints.

[aybarskeremtaskan]

Hi, thanks for the explanation.

I think the reason that extending the alternating strings (alt1 and alt2) work is that each time they transform into each other. (0101... becomes 1010... and vice versa etc.) which means that we should do diff2 = diff-1 and diff1 = diff2 -1 instead of diff -=1 and diff2-=1.

The solution works because at each round we take minimum of diff1 and diff2 which makes swapping diff1 and diff2 unnecessary computation wise (even though logically it seems wrong).

[mohaimenchowdhury]

It is great that you mentioned you have come up with that idea of type 1 operation from the leetcode discuss. It motivates people more that even NeetCodeIO looks for the leetcode discuss section, so why would we feel down to check the discuss section?

[seaDeeTea]

Great explanation! Just curious, were you able to solve it during the contest, or you spent time afterwards to come up with the solution?

[DroidHolicOfficial]

Beautiful Explanation man! One thing we can do to reduce the space is to double the string only when the given string is of odd length. I noticed that for even strings, doubling is of no use. i.e., type-1 operation is of no use at all. Only for odd strings we may get a minimum flip value by doing some type-1 operations.


s = s if k % 2 == 0 else s + s

[madhukiranattivilli]

This O(n) algo can be slightly improved with these changes :

Essentially, use bit manipulation operations

(1) No need to have an O(n) loop to build the alternating bits mask. Bit manipualation methods and geometric progression math formula can be used to get the mask bit string in O(1) time

(2) No need to have an O(n) loop to count bit flips. XOR of the input bit string segment and mask bit string segment can be done to get few 1 bits representing bit flips. Segments can be obtained by using an all 1s mask, AND with the input and alternating bits mask to get the segments, and right shift the all 1s mask to get the next segments. Later, the 1s in the XORed result can be obtained by using bit manipulation methods and geometric progression math formula -- build as many cloned blocks as is the length of the XORed result, AND each block with 1, 10, 100, ..., 1000 mask segments -- i.e. AND the 1st big block and the 2nd mask block -- right shift the ANDed block k times (where k is the length of the XORed block) to get all "bit flip indicator" bits (0 or 1) to the rightmost bit position

All these can be done mathematically. No need to code. Math equation (geometric progression) gives the result in O(1)

Thus the final program would be a much closer to O(n)

Makes sense? (I've implemented this)

[stefan.musarra]

My key take-away from this problem is that shifting elements from the beginning to the end (or the opposite) is the same as a sliding window on the string doubled. Thanks for showing us that brilliant observation/trick.

In this problem, if the string has an even length, you do not need to slide the window at all, but it essential to slide the window if the string has an odd length. Example: "11100" needs to be shifted 4 times but requires only 1 flip.

[akhilkhubchandani]

Thanks for this, keep posting every contest . Keeps me motivated

[ehsanmon]

Such a smart solution. Is this really a medium question though? It's pretty hard to come up with such a solution during an interview.

[deathbombs]

The key was seeing we can find answers by converting to a "target string", I thought there was some other trick to achieve alternating pattern, like checking for sequences

[siddharthsinghchauhan]

Aren't the string concatenation O(n^2) as they are immutable...

[hackytech]

Thankyou so Best explanation ever. Please keep posting for every contest 🙏

[amandubey]

Thankyou so much neetcode, I was scared of this question until this video. Thankyou so much for explaining the logic with such details.

[MCMCFan]

You can get rid of the diff1 and diff2. Since at each sliding Window diff1 +diff2 = n you can use res = min(res, diff, n - diff)

[alexgrossbard]

It is not necessary to check if left - right + 1 == n: res = min(res, diff1, diff2). You can do it at the bottom of the if left - right + 1 > n block since left will have been updated and that will make left - right + 1 == n

[maheswarreddy]

Clean explanation man thanks. Struggling to understand from leetcode discuss section.

[albertlee]

Thanks for the video, but I think there is a mistake in the code. The string concatenation creates new copies every time, so the time complexity of constructing alt1 and alt2 is O(n^2). I think the list operation should be used instead

[ZQutui]

Thanks for keeping up posting new solutions. Btw, what do you do as a software engineer? Web, Mobile, backend, or something else?

[udemezueiloabachie]

I always watch your explanation then I code my solution before wathcing your code solution.

[upendsingh]

to generate alt1 and alt2 we can use
alt1 = "01" * n
alt2 = "10" * n