Minimum flips to make a binary string alternate

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}