# Minimum Changes To Make Alternating Binary String
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string)
Canonical: https://scaleengineer.com/dsa/problems/minimum-changes-to-make-alternating-binary-string
**Data structures:** String
**Companies:** [Tesla](https://scaleengineer.com/companies/tesla)
---
## Problem
You are given a string `s` consisting only of the characters `'0'` and `'1'`. In one operation, you can change any `'0'` to `'1'` or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string `"010"` is alternating, while the string `"0100"` is not.

Return _the **minimum** number of operations needed to make_ `s` _alternating_.

**Example 1:**

**Input:** s = "0100"
**Output:** 1
**Explanation:** If you change the last character to '1', s will be "0101", which is alternating.

**Example 2:**

**Input:** s = "10"
**Output:** 0
**Explanation:** s is already alternating.

**Example 3:**

**Input:** s = "1111"
**Output:** 2
**Explanation:** You need two operations to reach "0101" or "1010".

**Constraints:**

* `1 <= s.length <= 104`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute Force by Generating Target Strings
This approach involves creating the two possible alternating target strings ("0101..." and "1010...") and then comparing the input string with each of them. The number of changes required for each target is the count of differing characters. The minimum of these two counts is the answer.
**Time:** O(n), where n is the length of the string. We have three loops that each run n times: one to build the target strings, and two implicit loops within the final comparison loop. This simplifies to O(n). · **Space:** O(n) to store the two generated target strings.
**Pros:** Simple to understand and implement.; The logic directly follows the problem definition.
**Cons:** Uses extra space proportional to the length of the input string to store the two target strings.; Less efficient than single-pass solutions that don't require extra storage.
### Explanation
The core idea is to materialize the two goal states. Any alternating binary string must either start with '0' or '1'.

- First, we construct a string `target1` that starts with '0' (e.g., "0101...").
- Second, we construct another string `target2` that starts with '1' (e.g., "1010...").
- Then, we iterate through the input string `s` and count how many characters need to be flipped to match `target1`. Let's call this `cost1`.
- We do the same for `target2` to get `cost2`.
- The final answer is the smaller value between `cost1` and `cost2`.

```java
class Solution {
    public int minOperations(String s) {
        int n = s.length();
        StringBuilder target1Builder = new StringBuilder();
        StringBuilder target2Builder = new StringBuilder();

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                target1Builder.append('0');
                target2Builder.append('1');
            } else {
                target1Builder.append('1');
                target2Builder.append('0');
            }
        }

        String target1 = target1Builder.toString();
        String target2 = target2Builder.toString();

        int changes1 = 0;
        int changes2 = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != target1.charAt(i)) {
                changes1++;
            }
            if (s.charAt(i) != target2.charAt(i)) {
                changes2++;
            }
        }

        return Math.min(changes1, changes2);
    }
}
```
### Algorithm
- Get the length `n` of the input string `s`.
- Create two `StringBuilder` objects, `target1Builder` and `target2Builder`.
- Loop from `i = 0` to `n-1`. In each iteration, append the correct alternating character to both builders. `target1Builder` gets '0' at even indices and '1' at odd indices. `target2Builder` gets '1' at even indices and '0' at odd indices.
- Convert the builders to strings `target1` and `target2`.
- Initialize two counters, `changes1` and `changes2`, to 0.
- Loop from `i = 0` to `n-1`.
  - Compare `s.charAt(i)` with `target1.charAt(i)`. If they are different, increment `changes1`.
  - Compare `s.charAt(i)` with `target2.charAt(i)`. If they are different, increment `changes2`.
- Return the minimum of `changes1` and `changes2`.

## Single Pass with Two Counters
This approach improves upon the brute-force method by avoiding the creation of the target strings. Instead of pre-building the target strings, we can determine the expected character at each position on-the-fly during a single pass through the input string. We maintain two counters to track the number of changes needed for each of the two possible alternating patterns.
**Time:** O(n), as we iterate through the string once. · **Space:** O(1), as we only use a few integer variables for counters, regardless of the input size.
**Pros:** Space-efficient, using only a constant amount of extra space.; Still conceptually simple and easy to follow.
**Cons:** The logic inside the loop is slightly more complex than the most optimal solution, with multiple conditional checks per iteration.
### Explanation
We can iterate through the string `s` just once. At each index `i`, we know what the character *should* be for both alternating patterns.

- For the pattern starting with '0' ("0101..."), the character at index `i` should be '0' if `i` is even, and '1' if `i` is odd.
- For the pattern starting with '1' ("1010..."), the character at index `i` should be '1' if `i` is even, and '0' if `i` is odd.
- We use two variables, `cost1` and `cost2`, to count the mismatches for each pattern. We iterate from `i = 0` to `n-1` and update the counters based on the character `s.charAt(i)`.
- Finally, we return `min(cost1, cost2)`. This eliminates the need for O(n) extra space.

```java
class Solution {
    public int minOperations(String s) {
        int n = s.length();
        int changes1 = 0; // Cost for pattern "0101..."
        int changes2 = 0; // Cost for pattern "1010..."

        for (int i = 0; i < n; i++) {
            // Check for pattern "0101..."
            if (i % 2 == 0) { // Even index, should be '0'
                if (s.charAt(i) == '1') {
                    changes1++;
                }
            } else { // Odd index, should be '1'
                if (s.charAt(i) == '0') {
                    changes1++;
                }
            }

            // Check for pattern "1010..."
            if (i % 2 == 0) { // Even index, should be '1'
                if (s.charAt(i) == '0') {
                    changes2++;
                }
            } else { // Odd index, should be '0'
                if (s.charAt(i) == '1') {
                    changes2++;
                }
            }
        }
        return Math.min(changes1, changes2);
    }
}
```
### Algorithm
- Initialize two counters, `changes1` (for "0101..." pattern) and `changes2` (for "1010..." pattern), to 0.
- Iterate through the input string `s` with index `i` from 0 to `n-1`.
- Inside the loop, check if `i` is even or odd.
- If `i` is even:
  - The "0101..." pattern expects '0'. If `s.charAt(i)` is '1', increment `changes1`.
  - The "1010..." pattern expects '1'. If `s.charAt(i)` is '0', increment `changes2`.
- If `i` is odd:
  - The "0101..." pattern expects '1'. If `s.charAt(i)` is '0', increment `changes1`.
  - The "1010..." pattern expects '0'. If `s.charAt(i)` is '1', increment `changes2`.
- After the loop, return `Math.min(changes1, changes2)`.

## Optimized Single Pass with One Counter
This is the most efficient approach. It builds on a key observation: the two target alternating strings ("0101..." and "1010...") are exact complements of each other. This means that if a character in the input string matches one pattern at a certain position, it must mismatch the other. Therefore, the sum of changes for both patterns is always equal to the length of the string (`n`). We only need to calculate the cost for one pattern and can derive the other.
**Time:** O(n), for a single pass over the string. · **Space:** O(1), as it only requires a single counter variable.
**Pros:** Most efficient in terms of both time and space.; O(1) space complexity.; O(n) time complexity with the minimum number of operations per iteration.; The code is clean and concise.
**Cons:** Relies on a clever observation (`cost1 + cost2 = n`) which might not be immediately obvious.
### Explanation
Let `cost1` be the number of operations to make the string "0101..." and `cost2` be the number of operations to make it "1010...".

- At any index `i`, if `s[i]` matches the character for the "0101..." pattern, it will not match the character for the "1010..." pattern, and vice-versa.
- This implies that for every index, there is exactly one mismatch when considering both patterns together.
- Summing over all indices, the total number of mismatches is `cost1 + cost2 = n`, where `n` is the length of the string.
- So, we can calculate just one of the costs, say `cost1`, by iterating through the string once. Then, `cost2` is simply `n - cost1`. The minimum operations will be `min(cost1, n - cost1)`.
- This simplifies the logic within the loop and reduces the number of comparisons.

```java
class Solution {
    public int minOperations(String s) {
        int n = s.length();
        int changes = 0; // Cost for pattern starting with '0' ("0101...")

        for (int i = 0; i < n; i++) {
            char expectedChar = (i % 2 == 0) ? '0' : '1';
            if (s.charAt(i) != expectedChar) {
                changes++;
            }
        }
        
        // The cost for the other pattern ("1010...") is n - changes.
        // We need the minimum of the two.
        return Math.min(changes, n - changes);
    }
}
```
### Algorithm
- Get the length `n` of the input string `s`.
- Initialize a single counter, `changes`, to 0. This counter will track the cost to transform `s` into the pattern starting with '0' ("0101...").
- Iterate through the string `s` with index `i` from 0 to `n-1`.
- In each iteration, determine the expected character for the "0101..." pattern. If `i` is even, it's '0'; if `i` is odd, it's '1'.
- Compare `s.charAt(i)` with the expected character. If they don't match, increment `changes`.
- After the loop, `changes` holds the cost for one pattern. The cost for the other pattern is `n - changes`.
- Return `Math.min(changes, n - changes)`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def minOperations(self, s: str) -> int: cnt = sum(c != '01' [i & 1] for i, c in enumerate(s)) return min(cnt, len(s) - cnt)

```