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

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: leetcode.com/problems/minimum...
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.

[@keremt8727]

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

[@akhilkhubchandani2632]

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

[@amandubey5287]

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

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

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

[@maheswarreddy3917]

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

[@KaKaphoebe]

very clear video. I like it. Thank you!

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

[@hackytech7494]

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

[@Ruslanpv6bs]

Super beatiful 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

[@Chirayu19]

I also thought the same, Nice!

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

[@ayushman_sinhaa]

Thank you so much! I Finally understood the problem

[@ankithreddyadudodla7673]

nice explanation!!!

[@amogchandrashekar8159]

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

[@NeetCode]

No problem!

[@udemezueiloabachie8626]

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

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

[@sairam3351]

Thank you so much bro.

[@siddharthsinghchauhan8664]

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

[@crit19871]

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

[@b_1729-j8j]

Thanks dude

[@abhinavsinghkushwah2416]

Thanks!

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

[@akashnarayan83]

Thank you

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

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

[@upendsingh9263]

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

[@arnabpersonal6729]

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

[@kanehtube5390]

ur videos are such a pretty ones.

[@vijaykumarlokhande1607]

keep posting.

[@victoriac7257]

Hey can you please do 1889 as well? Thanks!

[@neeldesai108]

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

[@RanjuRao]

Even I got TLE in java

[@user-zs1em2hm3p]

Similar, in C#

[@rajasbaadkar4989]

Use StringBuilder for alt1 and alt2

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

[@34_harshdeepraghuwanshi98]

Nice

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

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

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

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

[@Sulerhy]

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

[@khushboosharma1085]

👍

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

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

[@ygwg6145]

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

[@abukhandaker7558]

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

[@levimatheri7682]

Underrated comment 😂😂

[@user-zs1em2hm3p]

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