[LeetCode] 1758. Minimum Changes To Make Alternating Binary String

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

生成交替二进制字符串的最少操作数.

给你一个仅由字符 ‘0’ 和 ‘1’ 组成的字符串 s 。一步操作中，你可以将任一 ‘0’ 变成 ‘1’ ，或者将 ‘1’ 变成 ‘0’ 。
交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 “010” 是交替字符串，而字符串 “0100” 不是。
返回使 s 变成 交替字符串 所需的 最少 操作数。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-changes-to-make-alternating-binary-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一

这道题算是字符串类型的题目。我自己做的时候一开始没有想到太简洁的方法，所以分别模拟了 0101 和 1010 两种字符串，然后和 input 字符串比较，看看 diff1 小还是 diff2 小，小的那个就是最少操作数。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int minOperations(String s) {
        int n = s.length();
        char[] inputArray = s.toCharArray();
        char[] first = new char[n];
        boolean zero = true;
        for (int i = 0; i < n; i++) {
            if (zero) {
                first[i] = '0';
            } else {
                first[i] = '1';
            }
            zero = !zero;
        }


        boolean one = true;
        char[] second = new char[n];
        for (int i = 0; i < n; i++) {
            if (one) {
                second[i] = '1';
            } else {
                second[i] = '0';
            }
            one = !one;
        }

        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < n; i++) {
            if (inputArray[i] != first[i]) {
                count1++;
            }
            if (inputArray[i] != second[i]) {
                count2++;
            }
        }
        return Math.min(count1, count2);
    }
}

思路二

看了评论区的这个帖子，感觉最近还是题刷少了。他的思路是，最理想情况下，字符串应该是类似 01010101 这样的排列。在这种排列中，每个位置上的字符串与其下标 index 有如下关系，

index = 0, 1, 2, 3, 4 % 2
char = 0, 1, 0, 1, 0

所以我们可以遍历一遍 input 字符串，看一下每个位置的下标 index % 2 之后是否等于同位置上的字符串，记录全局不同的个数 diff。注意因为字符串可以是 0101 类型，也可以是 1010 类型的，所以我们需要看两种情况哪一种情况最优。假如 0101 类型需要操作的次数是 diff 的话，那么 1010 类型需要操作的次数 = 字符串长度 len - diff。比较这两者谁更小即可。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int minOperations(String s) {
        int n = s.length();
		int diff = 0;
        for (int i = 0; i < s.length(); i++) {
			if (i % 2 != s.charAt(i) - '0') {
				diff++;
			}
		}
		return Math.min(diff, n - diff);
    }
}