Minimum Number of Swaps to Make String Balanced - Leetcode 1963 Weekly Contest - Python

[@rommeltito123]

I have coded for 8+ years now and I still like watching these videos

[@RN-jo8zt]

me too ,because we don't do this stuff in our daily work

[@saranshthukral4021]

goat

[@YT.Nikolay]

I am super happy I solved myself, and did it slightly differently. Basically, I count opened and closed, and when closed > opened, I do a swap AND decrease closed AND increase opened counters. Accepted! =) def minSwaps(self, s: str) -> int: opened, closed = 0, 0 swaps = 0 for bracket in s: if bracket == '[': opened += 1 else: closed += 1 if closed > opened: swaps += 1 opened += 1 closed -= 1 return swaps

[@SkyeTian]

Thank you!

[@de-grafthazard9081]

Brilliant

[@ibragim1989]

To be honest your explanation even more intuitive. Thanks!

[@scoobyy3112]

This is such a good solution

[@mkycto]

I thought about that approach, but i cant't physically explain on case with s = "]]][[["

[@frida8519]

I just did this: class Solution: def minSwaps(self, s: str) -> int: flips, cSum = 0, 0; for b in s: if b == '[': cSum += 1; else: cSum -= 1; if cSum < 0: flips += 1; cSum = 1; return flips; Basically, if we ever have a negative sum, it means we have more closed brackets than we do open, so we have to make a swap and turn the ] into [, which means the current sum will be 1 again.

[@nitiketshinde1458]

even I went with same way initially, just the thing is that it goes few ms slower than the another way which is given in video.

[@user-fp4dr1ne7z]

A good question for a contest but a bad one for an interview. It such a difficult solution to come to on your own.

[@Abhishek-xr1xw]

I love the way he come up with the solution.

[@IAmIndraTheGod]

The simple intuitiion for this problem is that, 1. The number of open and closed brackets are same - given 2. They are just out of order, so we need to swap them - given 3. So how would you make it balanced, ? 4. It will become balanced once you swap the ones that are unbalanced. 5. So find out the brackets that are unbalanced, so we count closing brackets that dont have an associated open bracket. 6. We keep track of the maximum number of such closing brackets 7. since each swap would fix 2 of those closing brackets, we divide it by 2.

[@杨熙-v6v]

amazing！hope to solve neetcode all by following the series of video！

[@shantanukumar4081]

Great explanation 👍👍👍

[@bthulasikrishna9597]

Why increment by one? If we have odd number of unmatched, then (unmatched+1)//2 alternative is math.ceil(unbalanced/2)

[@adityaonytube9860]

works for even number of unmatched too right? like for eg. " ] ] [ [ " requries only 1 which is ((maxClose = 2) + 1)/2 ? Tho math.ceil works too

[@AustinWeeks]

This one took years off my life

[@MANOJKUMAR-mb2uw]

Why only adding +1 to closing brackets why not vice versa i tried it but showing error

[@jakjun4077]

I am confusing why u did divide instead of minus since u said every swap remove 2. what I know so far is every swap will reduce by two because it will turn to be balanced and only left the unbalance one to swap/solve. For example, 3 -> 1 could be achieved by minus 2 why divide by two. i am stucking at there. pls help

[@randomfool]

its the same thing bro, 100/2 = 50 means for every operation 100 is reduced by 2 so there are 50 such operations

[@ocoocososococosooooosoococoso]

i think theres people who can come up like this solution. Even after i solved nearly 300 leetcode and watched most of the tutorial of the videos, i could only start to solve the problem with a brute force, cannot come up with the optimized solution ever 😮‍💨

[@sankhadip_roy]

What is your current status?

[@shivangagrawal2923]

Best Explanation so far

[@sketchwithbratati4397]

Amazing. I could have never thought of it... How to come up with approaches on our own?

[@MGtvMusic]

Keep practising

[@rounakbhatia121]

amazing explanation

[@ashwinvarma9349]

but why increment by 1?

[@sanskartiwari2496]

I think of it as (maxClose //2) + (maxClose%2)

[@bthulasikrishna9597]

If we have odd number of unmatched, alternative is math.ceil(unbalanced/2)

[@WebDevAnjali]

I CAN NEVER THINK OF THIS SOLUTION EVEN WITHOUT THE ALGO ....I SPENT 2 HOURS BUT COULDN'T THINK OF RESOLVING ALL TEST CASE IT WILL GET STUCK IN ONE OR ANOTHER CASE ....

[@shubhamdeshmukh9287]

good work.

[@Live-hh6li]

Best explanation

[@akankshasharma7498]

How did you come up with that? great solution 🤟

[@aspiring_Sr.dev_Om]

Spoiler @ 4:32 MaxSwaps

[@johnj171]

youu broo love you

[@alisherkholmirzaev7885]

do we really need maxClose in the code? It is always 0 and I think it's enough to do (close + 1 ) / 2.

[@TechEats]

actually he did not explain need of maxClose. For test case ][][][, your logic will fail

[@ronifintech9434]

When you reach the end, close will be 0. So you need another variable

[@shubhamdeshmukh9287]

very nice.

[@AymenDaoudi-u6h]

It's wrong on many levels to ask such a question in an interview

[@jacksonripper-mp8dr]

Nobody cares about ur opinion....

[@ketansharma6955]

its quite similar to Minimum Add to Make Parentheses Valid

[@sainikhil956]

Thanks but can you please elaborate why did we use max variable ?

[@rohitbk7920]

to keep track of max of closecount at an instance

[@chenyixiang2424]

if we do not check the max variable, we may meet ]]][[[ and reach 0 in the end

[@mdanishossain026]

class Solution: def minSwaps(self, s: str) -> int: stack = [] for ch in s: if ch == '[': stack.append(ch) elif stack: stack.pop() return (len(stack)+1)//2 #approach_2: class Solution: def minSwaps(self, s: str) -> int: size = 0 for char in s: if char == '[': size += 1 elif size != 0 : size -= 1 return (size+1)//2

[@soumikghosh1522]

Solve 0-1 knapsack, other tutorials on youtube are not that clear

[@kritika_0204]

watch aditya verma dp series

[@aisharawat9102]

Mera dimaag kb chlega🥺🥺

[@nmkcomps]

What happens if I just take open brackets. Won’t your solution return 0

[@ssenthilnathan3]

I am afraid of Leetcode Weekly Contests because I don't know, I can solve it or not or maybe giveup in half-way. But I like the problems in leetcode and all other platforms. Don't judge me, I am an average human. Can anyone help me in this?

[@ssenthilnathan3]

@@BhanuTejaPogiri-rj3qp Thank you!

[@WebDevAnjali]

i used to think of myself as an average but since i've tried leetcode i come to know that i'm way below the bottom line 🙂i can't think of logics .... all the concepts of dp , recursive, tree or problems of knapsack or greedy approch i used to think of them in graphical way imagining in my head but during my academics i never even know those stuffs can be coded i hell have to idea how.... even being the easiest problem i get stuck quite often ....i wonder is it only me this stupid or there exists ppl ...i dont know how long will it take me to grab the problem solving flow or from where to begin with😭😭😭

[@sabukuna]

annoying problem

[@apoorvakumar2410]

this code doesn't work for multiple testcases

[@NeetCode]

sorry, you must have made a mistake. this exact code worked for me.

[@ytsh5752]

noice

[@eddiej204]

[@ameynaik2743]

Nice solution, can you please do video on 1055. Shortest Way to Form String from leetcode, I think there are multiple solutions possible for it.