# Minimum Number of Flips to Make the Binary String Alternating
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-flips-to-make-the-binary-string-alternating
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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 `s` and **append** it to the end of the string.
* **Type-2: Pick** any character in `s` and **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 <= 105`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute-Force Simulation of Rotations
This approach directly simulates the problem statement. Since Type-1 operations (rotations) are free, we can try every possible rotation of the string `s`. For each of these `n` rotations, we calculate the minimum number of Type-2 operations (flips) needed to make it alternating. The final answer is the minimum value found across all rotations.

For any given string, there are two possible alternating patterns it can be converted to: one starting with '0' (e.g., `"01010"`) and one starting with '1' (e.g., `"10101"`). We calculate the number of flips needed to achieve both patterns and take the smaller of the two. This process is repeated for all `n` rotations of the original string.
**Time:** O(N^2), where N is the length of the string. The outer loop runs N times for each rotation. The inner loop also runs N times to calculate the flips for the current rotation. · **Space:** O(N), where N is the length of the string. This space is used to store the mutable copy of the string (e.g., in a `StringBuilder`).
**Pros:** It is a straightforward implementation of the problem's logic.; Easy to understand and reason about.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5), leading to a 'Time Limit Exceeded' error on larger inputs.; It performs a lot of redundant calculations. The flip count for each rotation is calculated from scratch, while adjacent rotations share N-1 characters.
### Explanation
The algorithm iterates through all `n` possible cyclic shifts of the string `s`. In each iteration, it takes the current rotated string and computes the cost to transform it into an alternating string. The cost is the minimum of two values: the number of flips to match the `"0101..."` pattern and the number of flips to match the `"1010..."` pattern. The overall minimum cost found among all rotations is the result.

```java
class Solution {
    public int minFlips(String s) {
        int n = s.length();
        int minFlips = Integer.MAX_VALUE;
        StringBuilder sb = new StringBuilder(s);

        // Iterate through all n possible rotations
        for (int i = 0; i < n; i++) {
            // This is the i-th rotated string
            String current_s = sb.toString();
            
            // Calculate flips for the two possible alternating patterns
            int flipsToPattern01 = 0; // for "0101..."
            int flipsToPattern10 = 0; // for "1010..."
            
            for (int j = 0; j < n; j++) {
                // Target pattern starting with '0'
                if (current_s.charAt(j) != (j % 2 == 0 ? '0' : '1')) {
                    flipsToPattern01++;
                }
                // Target pattern starting with '1'
                if (current_s.charAt(j) != (j % 2 == 0 ? '1' : '0')) {
                    flipsToPattern10++;
                }
            }
            
            minFlips = Math.min(minFlips, Math.min(flipsToPattern01, flipsToPattern10));
            
            // Perform one rotation for the next iteration
            char firstChar = sb.charAt(0);
            sb.deleteCharAt(0);
            sb.append(firstChar);
        }
        
        return minFlips;
    }
}
```
### Algorithm
*   Initialize `min_flips` to a very large value.
*   Let `n` be the length of the input string `s`.
*   Create a mutable version of the string, for example, using `StringBuilder`.
*   Loop `n` times, from `i = 0` to `n-1`, to simulate each of the `n` possible rotations.
    *   In each iteration `i`, we have a new rotated string.
    *   Calculate the number of flips required to make this rotated string alternating. This requires two calculations:
        1.  `flips1`: Flips to match the pattern `"0101..."`.
        2.  `flips2`: Flips to match the pattern `"1010..."`.
    *   To calculate `flips1` and `flips2`, iterate from `j = 0` to `n-1` and compare the character at each position `j` with the expected characters of the two target patterns.
    *   Update `min_flips` with the minimum of its current value, `flips1`, and `flips2`.
    *   Perform one rotation on the string builder (move the first character to the end) to prepare for the next iteration.
*   After the loop finishes, `min_flips` will hold the minimum number of flips required for any rotation.

## Sliding Window on a Doubled String
A more efficient approach uses a sliding window technique to avoid re-calculating flips for each rotation. The key idea is that any rotation of `s` is a contiguous substring of length `n` in the string `s + s`. By creating this doubled string, we can find the minimum flips for all rotations by sliding a window of size `n` across it.

We can pre-calculate the mismatches for the entire doubled string against two fixed alternating patterns (`"0101..."` and `"1010..."`). Then, as we slide our window, we can update the total mismatches for the window in constant time by subtracting the contribution of the character that leaves the window and adding the contribution of the character that enters. This reduces the overall time complexity from quadratic to linear.
**Time:** O(N), where N is the length of the string. We iterate through the `2n` length string once to build mismatch arrays and then iterate `n` times for the sliding window, resulting in a linear time complexity. · **Space:** O(N), where N is the length of the string. This space is required to store the doubled string `s_double` and the two mismatch arrays.
**Pros:** Optimal time complexity of O(N), making it very efficient for large inputs.; Solves the problem elegantly by transforming the rotation problem into a sliding window problem.
**Cons:** Requires O(N) extra space, which might be a consideration for extremely large N in a memory-constrained environment.; The logic, while efficient, is less direct than the brute-force approach and requires careful handling of indices and patterns.
### Explanation
This optimized method avoids the O(N^2) complexity by recognizing that rotations can be viewed as a sliding window. 

1.  **Doubled String**: We first create a string `s_double` of length `2n` by appending `s` to itself. Any cyclic shift of `s` will appear as a substring of length `n` in `s_double`.
2.  **Mismatch Arrays**: We define two target alternating patterns that extend to length `2n`: `target1 = "0101..."` and `target2 = "1010..."`. We then create two boolean/integer arrays, `mismatches1` and `mismatches2`, where `mismatches1[i]` is 1 if `s_double[i]` does not match `target1[i]`, and similarly for `mismatches2`. This takes O(N) time.
3.  **Sliding Window Sum**: We calculate the number of flips for the first window (the original string `s`) by summing the first `n` elements of the mismatch arrays. Then, we slide the window one position at a time. For each slide, we update the flip counts in O(1) by subtracting the mismatch of the outgoing element and adding the mismatch of the incoming element. For each window, we find the minimum of the two flip counts and update our global minimum.

An important insight is that for any window starting at index `i`, the minimum flips will be `min(current_flips1, current_flips2)`, where `current_flips1` and `current_flips2` are the sums of the mismatch arrays over that window. This holds true regardless of the parity of `i` because if the starting index `i` has a different parity, the roles of the two target patterns effectively swap, but the minimum of the two costs remains the same.

```java
class Solution {
    public int minFlips(String s) {
        int n = s.length();
        String s2 = s + s;
        int len2 = 2 * n;
        
        // Mismatches for target "0101..." (pattern1)
        int[] mismatches1 = new int[len2];
        // Mismatches for target "1010..." (pattern2)
        int[] mismatches2 = new int[len2];
        
        for (int i = 0; i < len2; i++) {
            if (s2.charAt(i) != (i % 2 == 0 ? '0' : '1')) {
                mismatches1[i] = 1;
            }
            if (s2.charAt(i) != (i % 2 == 0 ? '1' : '0')) {
                mismatches2[i] = 1;
            }
        }
        
        int flips1 = 0; // Flips for the current window vs pattern1
        int flips2 = 0; // Flips for the current window vs pattern2
        
        // Calculate flips for the initial window (the original string)
        for (int i = 0; i < n; i++) {
            flips1 += mismatches1[i];
            flips2 += mismatches2[i];
        }
        
        int minFlips = Math.min(flips1, flips2);
        
        // Slide the window across the doubled string
        for (int i = 1; i < n; i++) {
            // Update flip counts in O(1)
            flips1 = flips1 - mismatches1[i - 1] + mismatches1[i + n - 1];
            flips2 = flips2 - mismatches2[i - 1] + mismatches2[i + n - 1];
            
            minFlips = Math.min(minFlips, Math.min(flips1, flips2));
        }
        
        return minFlips;
    }
}
```
### Algorithm
*   Let `n` be the length of `s`.
*   Create a new string `s_double` by concatenating `s` with itself (`s + s`). This string of length `2n` contains all possible rotations of `s` as substrings of length `n`.
*   Create two helper arrays, `mismatches1` and `mismatches2`, each of length `2n`.
    *   `mismatches1[i]` is 1 if `s_double[i]` differs from the `"0101..."` pattern at index `i`, 0 otherwise.
    *   `mismatches2[i]` is 1 if `s_double[i]` differs from the `"1010..."` pattern at index `i`, 0 otherwise.
*   Initialize `flips1` and `flips2` by summing the first `n` elements of `mismatches1` and `mismatches2`, respectively. This gives the flip counts for the original, un-rotated string.
*   Initialize `min_flips = min(flips1, flips2)`.
*   Iterate from `i = 1` to `n-1` to slide a window of size `n` across `s_double`.
    *   In each step, update `flips1` and `flips2` in O(1) time by subtracting the mismatch value of the character leaving the window and adding the mismatch value of the character entering the window.
    *   The characters are `s_double[i-1]` (leaving) and `s_double[i+n-1]` (entering).
    *   After each update, update `min_flips = min(min_flips, flips1, flips2)`.
*   Return `min_flips`.

# Solutions
### Java

```java
class Solution {
public
  int minFlips(String s) {
    int n = s.length();
    String target = "01";
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) != target.charAt(i & 1)) {
        ++cnt;
      }
    }
    int ans = Math.min(cnt, n - cnt);
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) != target.charAt(i & 1)) {
        --cnt;
      }
      if (s.charAt(i) != target.charAt((i + n) & 1)) {
        ++cnt;
      }
      ans = Math.min(ans, Math.min(cnt, n - cnt));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minFlips(string s) {
    int n = s.size();
    string target = "01";
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] != target[i & 1]) {
        ++cnt;
      }
    }
    int ans = min(cnt, n - cnt);
    for (int i = 0; i < n; ++i) {
      if (s[i] != target[i & 1]) {
        --cnt;
      }
      if (s[i] != target[(i + n) & 1]) {
        ++cnt;
      }
      ans = min({ans, cnt, n - cnt});
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minFlips(self, s: str) -> int: n = len(s) target = "01" cnt = sum(c != target[i & 1] for i, c in enumerate(s)) ans = min(cnt, n - cnt) for i in range(n): cnt -= s[i] != target[i & 1] cnt += s[i] != target[(i + n) & 1] ans = min(ans, cnt, n - cnt) return ans

```