Problem Statement
Given a binary string s containing only 0 and 1, the task is to find the minimum number of bit flips required to make the string alternating.
A binary string is called alternating when no two adjacent characters are the same.
A bit flip means changing:
0to11to0
The goal is to make the string alternating using the minimum number of flips.
Examples
Example 1:
Input: s = "001"
Output: 1
Explanation: By flipping the character at index 0, the string becomes "101", which is alternating. Therefore, only one flip is required.
Example 2:
Input: s = "0001010111"
Output: 2
Explanation: By flipping the characters at indices 1 and 8, the string becomes "0101010101", which is alternating. Therefore, the minimum number of flips required is 2.
Approach: Compare Two Alternating Patterns
An alternating binary string can only follow one of two patterns:
010101010...101010101...
Instead of generating new strings, both patterns can be checked by comparing the expected character at each index with the actual character in the input string.
Two counters are maintained:
flip0– counts the number of mismatches when the expected pattern starts with0.flip1– counts the number of mismatches when the expected pattern starts with1.
At every index, the expected character for both patterns is calculated using the index parity (i % 2).
After traversing the string, the smaller of the two flip counts is returned.
Step-by-step algorithm
- Initialize two counters,
flip0andflip1, to0. - Traverse the string from index
0tos.Length - 1. - For the first pattern (
0101...):- At even indices, the expected character is
0. - At odd indices, the expected character is
1.
- At even indices, the expected character is
- For the second pattern (
1010...):- At even indices, the expected character is
1. - At odd indices, the expected character is
0.
- At even indices, the expected character is
- If the actual character doesn't match the expected character, increment the corresponding counter.
- Return
Math.Min(flip0, flip1).
C# Code
class Solution
{
public int minFlips(string s)
{
int flip0 = 0;
int flip1 = 0;
for (int i = 0; i < s.Length; i++)
{
char expected0 = (i % 2 == 0) ? '0' : '1';
char expected1 = (i % 2 == 0) ? '1' : '0';
if (s[i] != expected0)
flip0++;
if (s[i] != expected1)
flip1++;
}
return Math.Min(flip0, flip1);
}
}Code Explanation
1. Initialize the counters
int flip0 = 0;
int flip1 = 0;Two integer variables are created to count the required flips for the two possible alternating patterns.
flip0tracks flips for010101....flip1tracks flips for101010....
2. Traverse the string
for (int i = 0; i < s.Length; i++)The loop traverses each character of the string exactly once. The index i is used to determine whether the current position is even or odd.
3. Calculate the expected characters
char expected0 = (i % 2 == 0) ? '0' : '1';
char expected1 = (i % 2 == 0) ? '1' : '0';The modulo operator % is used to determine the parity of the index.

Join the conversation! Your thoughts help the community grow.