Minimum flips to make a binary string alternate
Problem
Return the minimum number of characters to flip so that no two adjacent characters of the binary string are equal.
Example 1
Input: "0001010111" Output: 2
Flip to "0101010101".
Also asked as: Number of flips to make binary string alternate
Test cases
Case 1
Input: "0001010111" Expected: 2
Case 2
Input: "1111" Expected: 2
Case 3
Input: "0101" Expected: 0
Case 4
Input: "1" Expected: 0
View solutionHide solution1 approach
1. Compare against both alternating patterns
Time O(n)Space O(1)
Count mismatches versus "0101…"; mismatches versus "1010…" is n minus that. Answer is the smaller.
function minFlips(s) { let diff = 0; for (let i = 0; i < s.length; i++) { const expected = i % 2 === 0 ? '0' : '1'; if (s[i] !== expected) diff++; } return Math.min(diff, s.length - diff);}