Minimum Number of Changes to Make Binary String Beautiful - Leetcode 2914 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:05 - Coding Explanation
7:13 - Drawing Explanation
9:15 - Coding Explanation

leetcode 2914

#neetcode #leetcode #python

[yang]

Looking at these integers as pairs is the key to solving the problem

[nirmalgurjar]

Using binary operation xor makes its highly efficient:

public int minChanges(String s) {

int ans = 0, i = 0;

while (i < s.length()) {
ans += s.charAt(i++) ^ s.charAt(i++); // gives 1 when last digit is set and unset in any one position
}

return ans;
}

[codewithven]

# simpler approach
def minChanges(self, s: str) -> int:
res = 0

for i in range(1, len(s), 2):
if s[i] != s[i - 1]:
res += 1

return res

[Tates]

the problem statement of this question is horrible tho

[codewithven]

"""
Dynamic Programming Approach
10 01 01 10
dp[0] = 1
dp[1] = 1 + 1 = 2
dp[2] = 1 + 2 = 3
dp[3] = 1 + 3 = 4

then dp[x] = (check curr substring if same then 0 else 1) + dp[x - 1]
"""
def minChanges(self, s: str) -> int:
sLen = len(s)
dp = [0] * ((sLen // 2) + 1)

for i in range(1, sLen, 2):
curr = 0 if s[i] == s[i - 1] else 1
dp[(i + 1) // 2] = curr + dp[((i + 1) // 2) - 1]

return dp[sLen // 2]

[vitruvius]

Ok I tried solving this with top-down DP (so recursion + memoization), but I keep getting time limit exceeded. Has anyone else found that top-down DP leads them to getting the TLE issue more time than not when submitting their solution on Leetcode?

[itsjustramblings]

the problem should have mentioned minimum no of flips, makes it a little bit clearer.

[krishnapate]

Why you use two pointer method it is already clarified that string will be evern so literally increment for loop i=i+2 and s[i] and s[i+1] if they are not equal just count++ and in last return count 👍

[akashverma]

Greedy Algorithm has always been nightmare for me.

[sanketkadam]

You should not have removed the code solutions from the website , really disappointed by that, i was half way through solving questions and now i am not able to practice properly and the price is too high, being from india i can't afford that price

[aayushtheapple]

Man, after 30 minutes I arrived at following recursion with memo solution :
```
class Solution3:
def minChanges(self, s: str) -> int:
# recursion with memo
def solve(index, isOne, subStrSize):
if index == len(s):
return 0
# alter character
# do not alter character
if isOne and (index, subStrSize) in self.cacheOne:
return self.cacheOne[(index, subStrSize)]
if not isOne and (index, subStrSize) in self.cacheZero:
return self.cacheZero[(index, subStrSize)]
res = float("inf")
if isOne:
if s[index] == "1":
# do not alter character
if (subStrSize + 1) % 2 == 0:
# now subStr is even
res = min(solve(index + 1, True, 0), solve(index + 1, False, 0))
else:
# now subStr is odd
res = min(res, solve(index + 1, isOne, subStrSize + 1))
else:
# do alter character
if (subStrSize + 1) % 2 == 0:
# now subStr is even
res = min(1 + solve(index + 1, True, 0), 1 + solve(index + 1, False, 0))
else:
# now subStr is odd
res = min(res, 1 + solve(index + 1, isOne, subStrSize + 1))
self.cacheOne[(index, subStrSize)] = res
else:
if s[index] == "0":
# do not alter character
if (subStrSize + 1) % 2 == 0:
# now subStr is even
res = min(solve(index + 1, True, 0), solve(index + 1, False, 0))
else:
# now subStr is odd
res = min(res, solve(index + 1, isOne, subStrSize + 1))
else:
# do alter character
if (subStrSize + 1) % 2 == 0:
# now subStr is even
res = min(1 + solve(index + 1, True, 0), 1 + solve(index + 1, False, 0))
else:
# now subStr is odd
res = min(res, 1 + solve(index + 1, isOne, subStrSize + 1))
self.cacheZero[(index, subStrSize)] = res
return res
self.cacheOne = {}
self.cacheZero = {}
return min(solve(0, True, 0), solve(0, False, 0))
```

And after watching the first 4 minutes of your video I was here :
```
class Solution:
def minChanges(self, s: str) -> int:
changes = 0
for i in range(0, len(s), 2):
if s[i] != s[i+1]:
changes += 1
return changes
```

Thanks a lot!