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

[@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).

[@dheepthaaanand3214]

Thank you for this! Yes, when we are considering 110001, we would want to compare it with 010101 as well, but that comes by shifting 101010, the 2nd possible alternation. And so the diff is technically 4 becoming 2 as we should compare diff with the same alternation

[@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.

[@madhukiranattivilli2321]

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)

[@amandubey5287]

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

[@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

[@Chirayu19]

I also thought the same, Nice!

[@akhilkhubchandani2632]

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

[@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?

[@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

[@hackytech7494]

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

[@ducthinh2412]

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

[@maheswarreddy3917]

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

[@alexgrossbard6206]

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

[@udemezueiloabachie8626]

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

[@upendsingh9263]

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

[@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.

[@amogchandrashekar8159]

Thanks for this, I was about to request this in comments!

[@NeetCode]

No problem!

[@neeldesai108]

Just FYI, Same implementation in Java returns TLE Thanks, ndesai

[@RanjuRao]

Even I got TLE in java

[@AymenDaoudi-u6h]

Similar, in C#

[@rajasbaadkar4989]

Use StringBuilder for alt1 and alt2

[@arnabpersonal6729]

we can get alt values by using '01'*n and '10'*n

[@siddharthsinghchauhan8664]

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

[@KaKaphoebe]

very clear video. I like it. Thank you!

[@Ruslanpv6bs]

Super beatiful solution!

[@sidazhong2019]

if (r-l+1)==n: res = min(res,diff1,diff2) This if condition is unnecessary, since the left pointer has already been increment. it's just like if (10-0+1>10), again if (10-1+1)==10 in the same loop. so completly waste. you can just put " res = min(res,diff1,diff2) " inside of the prev if condition.

[@abukhandaker7558]

We will watch the problem or the ads? Seems like greedy algorithm

[@levimatheri7682]

Underrated comment 😂😂

[@albertlee5648]

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

[@ayushman_sinhaa]

Thank you so much! I Finally understood the problem

[@ZQutui]

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

[@AbhishekJaiswal24]

He is completely anonymous for us , he works at Google

[@crit19871]

Thanks for your content. Your solutions are amazing. Could you please make a video on Subarray sum equals K.

[@kanehtube5390]

ur videos are such a pretty ones.

[@hieijaganshi7088]

I don't understand why its impossible to get a better solution by performing type-1 operations, then type-2 operations, then type-1 operations (etc) VS just performing all the type-1 operations and then all the type-2 operations

[@sairam3351]

Thank you so much bro.

[@0088abs]

Nice way to explain , but I think this is not the optimal solution and errors out for a test case having around 74461 characters in input . Error- :Time limit exceeded" . Kindly update the code with the upgraded version if any . It would be really helpful if there can be a direct link for the source code as well . Thanks, your videos are helpful !!!

[@akashnarayan83]

Thank you

[@b_1729-j8j]

Thanks dude

[@joeycopperson]

Does anyone know why string is added to original only once? How does duplicating string solve the problem? Is it coz string comprise of '0' and '1' (only 2 types of digits) ?

[@siddharth4069]

Cause its a cyclic problem. You are allowed to remove characters from the front of the string and attach to the back. Thus this will lead to the possibility of multiple different strings from a single string of length "n". If we attach the string to itself and then look at all "n" length substrings of the s, we can look at all possibilities of strings that we could have formed by removing characters from the front of the string and attaching to the end.

[@victoriac7257]

Hey can you please do 1889 as well? Thanks!

[@yogendrakesharwani3650]

This is not medium level question it very very hard for anyone to come up with this type of solution by it's own

[@ankithreddyadudodla7673]

nice explanation!!!

[@abhinavsinghkushwah2416]

Thanks!

[@vijaykumarlokhande1607]

keep posting.

[@AymenDaoudi-u6h]

Efficient ?! it shows 1232ms right there, and it LTEs in other languages. But good explanation thank you.

[@Sulerhy]

double size of list -> too brilliant. I know the solution, but I can't figure it out how to code it effectively.

[@ygwg6145]

Actually diff1 + diff2 == L. Only one diff/alt is needed.

[@SmoothCode]

What is the purpose of s = s+ s ? What does it help us with?

[@siddharth4069]

Cause its a cyclic problem. You are allowed to remove characters from the front of the string and attach to the back. Thus this will lead to the possibility of multiple different strings from a single string of length "n". If we attach the string to itself and then look at all "n" length substrings of the s, we can look at all possibilities of strings that we could have formed by removing characters from the front of the string and attaching to the end.

[@34_harshdeepraghuwanshi98]

Nice

[@khushboosharma1085]

👍