1758. Minimum Changes To Make Alternating Binary String #

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'.

Problem Summary #

You will be given a string s containing only the characters “0” and “1”. In one operation, you can change any '0' to '1', or vice versa. If no two adjacent characters are equal, the string is called an alternating string. For example, the string “010” is alternating, while the string “0100” is not. Return the minimum number of operations needed to make s alternating.

Solution Approach #

• Easy problem. Use the parity alternation of array indices to determine an alternating string. There are 2 types of alternating strings: one is '01010101……' and the other is '1010101010……'. You only need to calculate one of them; for the other one, len(s) - res is the answer.

Code #

package leetcode

func minOperations(s string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		if int(s[i]-'0') != i%2 {
			res++
		}
	}
	return min(res, len(s)-res)
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}