Minimum Changes To Make Alternating Binary String

EASY

Description

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 <= 10⁴
s[i] is either '0' or '1'.

Approaches

Checkout 3 different approaches to solve Minimum Changes To Make Alternating Binary String. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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);
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(n) to store the two generated target strings.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Changes To Make Alternating Binary String. Click on different languages to view the code.

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);
  }
}

Video Solution

Watch the video walkthrough for Minimum Changes To Make Alternating Binary String

Data Structures:

String

Companies:

Tesla |