LC1758: Minimum Changes To Make Alternating Binary String

Date: 2026-03-05
Difficulty: EASY
Attempts: 1
Solution link: N/A
Question link: https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string?envType=daily-question&envId=2026-03-05

Intuition

Just iterate through the string and count. That’s it.

There are two possible output for each input, you just need to find the optimal one between the two. Takes, for example:

INPUT: 1011

There are two possible ways to do this: 1010 (1 change) and 0101 (3 changes). Since the question ask for minimum changes, we return 1.

There are three conclusions we can make:

1. Sum of the two solution length are the input string length.
2. Because of 1, an optimal (smaller number of changes) solution will never bigger than s.length() / 2

You probably know what to do next from here.

Approach

You just need to iterate through the string and test for one solution. If it excess half the string length, return s.length() - count.

Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Code

class Solution {
    public int minOperations(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (i % 2 == chars[i] - 48) {
                count++;
            }
        }
        if (count > length / 2) {
            return length - count;
        } else {
            return count;
        }
    }
}

Note

Instead of testing if count excess half the string length, you can just calculate the other solution and return the smaller one.

- if (count > length / 2) {
-         return length - count;
-     } else {
-         return count;
-     }
+ return Math.min(count, length - count);

I… originally didn’t think of this.