使二进制字符串变美丽的最少修改次数
难度:
标签:
题目描述
You are given a 0-indexed binary string s having an even length.
A string is beautiful if it's possible to partition it into one or more substrings such that:
- Each substring has an even length.
- Each substring contains only
1's or only0's.
You can change any character in s to 0 or 1.
Return the minimum number of changes required to make the string s beautiful.
Example 1:
Input: s = "1001" Output: 2 Explanation: We change s[1] to 1 and s[3] to 0 to get string "1100". It can be seen that the string "1100" is beautiful because we can partition it into "11|00". It can be proven that 2 is the minimum number of changes needed to make the string beautiful.
Example 2:
Input: s = "10" Output: 1 Explanation: We change s[1] to 1 to get string "11". It can be seen that the string "11" is beautiful because we can partition it into "11". It can be proven that 1 is the minimum number of changes needed to make the string beautiful.
Example 3:
Input: s = "0000" Output: 0 Explanation: We don't need to make any changes as the string "0000" is beautiful already.
Constraints:
2 <= s.length <= 105shas an even length.s[i]is either'0'or'1'.
代码结果
运行时间: 38 ms, 内存: 16.2 MB
/*
* 思路：
* 使用Java Stream API处理字符串，
* 将字符串按每两个字符分组，然后检查这些分组中是否有相同字符。
* 如果有则需要修改字符，统计修改次数。
*/
import java.util.stream.IntStream;
public class Solution {
public int minChangesToMakeBeautiful(String s) {
return (int) IntStream.range(0, s.length() / 2)
.filter(i -> s.charAt(2 * i) == s.charAt(2 * i + 1))
.count();
}
}解释
方法:
该题解的核心思路是检查字符串中相邻的字符是否相同。由于要求每个美丽子字符串只包含相同的字符且长度是偶数，我们可以将字符串视为由多个两个字符组成的子串来检查。对于每一个从索引1开始的奇数索引，如果它与前一个字符（偶数索引）不同，那么至少需要更改其中一个字符来确保这两个字符相同，从而使得从这个偶数索引开始的两个字符长的子串成为美丽的。通过这种方式，我们可以计算出整个字符串中需要修改的最小字符数，从而使整个字符串变为美丽的。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择从索引1开始，并且每隔一个元素进行检查，这种方法有什么特别的原因吗？
▷🦆
在这种解法中，如果遇到连续的奇数个相同字符如何处理？例如字符串 '111' 应该如何修改以满足题目要求？
▷🦆
解法中只考虑每两个相邻字符是否相同，那么整个字符串的长度是否一定会是偶数，如果是奇数长度的字符串该如何处理？
▷