Description
You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:
- Type-1: Remove the character at the start of the string
sand append it to the end of the string. - Type-2: Pick any character in
sand flip its value, i.e., if its value is'0'it becomes'1'and vice-versa.
Return the minimum number of type-2 operations you need to perform such that s becomes alternating.
The string is called alternating if no two adjacent characters are equal.
- For example, the strings
"010"and"1010"are alternating, while the string"0100"is not.
Example 1:
Input: s = "111000" Output: 2 Explanation: Use the first operation two times to make s = "100011". Then, use the second operation on the third and sixth elements to make s = "101010".
Example 2:
Input: s = "010" Output: 0 Explanation: The string is already alternating.
Example 3:
Input: s = "1110" Output: 1 Explanation: Use the second operation on the second element to make s = "1010".
Constraints:
1 <= s.length <= 105s[i]is either'0'or'1'.
Solutions
This optimized solution uses a sliding window approach with an array op to track flip counts for both parity groups. It first counts the total flips needed for both alternating patterns by using charCodeAt and XOR operations to determine parity. Then it slides through each position, removing the contribution of the left element and adding the contribution of a hypothetical right element at position n + i, incrementally updating the counts. This allows it to find the minimum flips needed in a single linear pass after the initial setup.
/**
* @param {string} s
* @return {number}
*/
var minFlips = s => {
const n = s.length;
const op = [0, 0];
let res = n;
for (let i = 0; i < n; i++) {
op[(s.charCodeAt(i) ^ i) & 1]++;
}
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i);
op[(c ^ i) & 1]--;
op[(c ^ (n + i)) & 1]++;
res = Math.min(res, ...op);
}
return res;
};