2914. Minimum Number of Changes to Make Binary String Beautiful

LeetCode 力扣

1. Description

Given a binary string s of even length, find the fewest character changes needed to make it beautiful. Each change replaces one character with ‘0’ or ‘1’.
A beautiful string can be split into one or more contiguous substrings, each of even length and containing only zeros or only ones.
Return the minimum number of changes.

2. Example

Example 1

Input: s = “1001”
Output: 2
Explanation: Change s[1] to ‘1’ and s[3] to ‘0’, obtaining “1100”. Splitting it into “11” and “00” meets both requirements, and two changes are necessary.

Example 2

Input: s = “10”
Output: 1
Explanation: Change s[1] to ‘1’ to obtain the beautiful string “11”.

Example 3

Input: s = “0000”
Output: 0
Explanation: The original string already qualifies as a single substring, so no changes are needed.

3. Constraints

  • 2 <= s.length <= 10$^5$
  • s has an even length.
  • s[i] is either ‘0’ or ‘1’.

4. Solutions

Greedy

n = str.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int minChanges(const string &str) {
        const int n = str.size();

        int count = 0;
        for (int left = 0, right = 1; right < n; left += 2, right += 2) {
            count += static_cast<int>(str[left] != str[right]);
        }

        return count;
    }
};
comments powered by Disqus