1888. Minimum Number of Flips to Make the Binary String Alternating
Approach
Double the string; sliding window of length n; track flip costs for both patterns.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: Double the string; sliding window of length n; track flip costs for both patterns.
// Time: O(n) Space: O(n)
public class Solution
{
public int MinFlips(string s)
{
int n = s.Length;
// count[0][0] := the number of 0s in the even indices
// count[0][1] := the number of 0s in the odd indices
// count[1][0] := the number of 1s in the even indices
// count[1][1] := the number of 1s in the odd indices
int[,] count = new int[2, 2];
for (int i = 0; i < n; ++i)
count[s[i] - '0', i % 2]++;
// min(make all 0s in the even indices + make all 1s in the odd indices,
// make all 1s in the even indices + make all 0s in the odd indices)
int ans = Math.Min(count[1, 0] + count[0, 1], count[0, 0] + count[1, 1]);
for (int i = 0; i < n; ++i)
{
count[s[i] - '0', i % 2]--;
count[s[i] - '0', (n + i) % 2]++;
ans = Math.Min(ans, Math.Min(count[1, 0] + count[0, 1], count[0, 0] + count[1, 1]));
}
return ans;
}
}