Check aligned pairs
class Solution: def minChanges(self, s): changes = 0 for i in range(0, len(s), 2): if s[i] != s[i + 1]: # one flip fixes this pair changes += 1 return changes
The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.
Six barges in a canyon lock show why extending the same run from opposite ends gives different results. Watch the gates split a matching chamber into pairs, then use those pairs to count the fewest changes a binary string needs.
class Solution: def minChanges(self, s): n = len(s) # best[end] = fewest changes to make s[:end] beautiful best = [0] + [float("inf")] * n for end in range(2, n + 1, 2): ones = 0 for start in range(end - 2, -1, -2): # grow the last block s[start:end] two chars left ones += (s[start] == "1") + (s[start + 1] == "1") zeros = (end - start) - ones # flip the minority so the block is all one digit cost = min(ones, zeros) best[end] = min(best[end], best[start] + cost) return best[n]