Devin's Blog

Minimum Number Of Flips To Make The Binary String Alternating

2 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • Find the minimum number of flips needed for every possible rotation
  • You can put the first element at the end, which is free.
  • So if you were thinking in a brute force fashion, you would think:
    • Check for every possible rotation of an element to the end the number of flips possible, then return the minimum.
  • But what tool should you apply to achieve this? First of all, we ask: how do I move an element from beginning to end?
    • Original thoughts were:
      • Deque
      • Modulo wrap around
  • However, a better question in this case is:
  • A sliding window can only take in contiguous elements.
  • The trick in this case is:
    • Just copy the string twice, then apply sliding window.
  • Then:
    • Slide the window with constant size, checking each time against the bit mask with 0 first and bitmask with 1 first, i.e. 01010101 vs. 1010101…

Complexity

Runtime

since we are sliding our window on size 2N, where N = len(s)

Space

to cast the string into an array (since that is more efficient instead of performing string manipulation).

Code

class Solution:
    def minFlips(self, s: str) -> int:
        nums = [int(s[i]) for i in range(len(s))]
        n = len(nums)
        nums.extend(nums)  # Duplicate the string to handle rotation
 
        # Creating bitmasks for zero-first and one-first patterns
        zero_first_bm = [1] * len(nums)
        one_first_bm = [0] * len(nums)
        for i in range(len(nums)):
            if i % 2 == 0:
                zero_first_bm[i] = 0
                one_first_bm[i] = 1
 
        left = 0
        zfc = ofc = 0
        cur_min = n  # Initialize with maximum flips possible (length of the string)
        for right in range(len(nums)):
            if nums[right] != zero_first_bm[right]:
                zfc += 1
            if nums[right] != one_first_bm[right]:
                ofc += 1
            
            if right >= n:  # Adjust the window size to maintain length n
                if nums[left] != zero_first_bm[left]:
                    zfc -= 1
                if nums[left] != one_first_bm[left]:
                    ofc -= 1
                left += 1
            
            if (right - left + 1) == n:
                cur_min = min(cur_min, zfc, ofc)
            
        return cur_min

Notes

Cards

START Basic Front: Minimum Number Of Flips To Make The Binary String Alternating Back: Extend array with copy of itself, then compare against bitmask.

END

References

Graph View