Minimum Number of Flips to Reverse Binary String

Difficulty: Easy | Acceptance: 76.40% | Paid: No Topics: Math, Two Pointers, String, Bit Manipulation

You are given a binary string s. Return the minimum number of flips needed to make s equal to its reverse. A flip changes a ‘0’ to ‘1’ or a ‘1’ to ‘0’.

• Examples
• Constraints
• Two Pointers
• Direct Comparison
• Iterative

Examples

Example 1

Input:

n = 7

Output:

0

Explanation: The binary representation of 7 is “111”. Its reverse is also “111”, which is the same. Hence, no flips are needed.

Example 2

Input:

n = 10

Output:

4

Explanation: The binary representation of 10 is “1010”. Its reverse is “0101”. All four bits must be flipped to make them equal. Thus, the minimum number of flips required is 4.

Constraints

1 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Two Pointers

Intuition Use two pointers starting from both ends of the string, comparing characters and counting mismatches until they meet in the middle.

Steps

• Initialize left = 0, right = n - 1, and flips = 0
• While left < right:
  • If s[left] != s[right], increment flips
  • Move left right and right left
• Return flips

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        left, right = 0, n - 1
        flips = 0
        
        while left < right:
            if s[left] != s[right]:
                flips += 1
            left += 1
            right -= 1
        
        return flips

Complexity

• Time: O(n) - We traverse the string once
• Space: O(1) - Only using constant extra space
• Notes: Optimal solution with minimal space usage

Direct Comparison

Intuition Compare the string with its reverse and count differences, then divide by 2 since each mismatched pair is counted twice.

Steps

• Create the reverse of the string
• Count positions where original and reverse differ
• Return count / 2

class Solution:
    def minFlips(self, s: str) -> int:
        reversed_s = s[::-1]
        diff = sum(1 for a, b in zip(s, reversed_s) if a != b)
        return diff // 2

Complexity

• Time: O(n) - Creating reverse and comparing
• Space: O(n) - Storing the reversed string
• Notes: Uses extra space for the reversed string

Iterative

Intuition Iterate through the first half of the string and compare each character with its mirror position from the end.

Steps

• Initialize flips = 0
• For i from 0 to n/2 - 1:
  • If s[i] != s[n-1-i], increment flips
• Return flips

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        flips = 0
        
        for i in range(n // 2):
            if s[i] != s[n - 1 - i]:
                flips += 1
        
        return flips

Complexity

• Time: O(n) - We traverse half the string
• Space: O(1) - Only using constant extra space
• Notes: Clean and intuitive approach