← leetcode

Minimum Number of Changes to Make Binary String Beautiful

· Medium

LeetCode problem 2914

realise that to make the string beautiful in the minimum number of changes, we just need to iterate through every 2 letters and check whether or not they are the same.

this works because every part of a beautiful string has an even length, so each part starts at an even index, and each pair s[i], s[i+1] (for even i) sits inside a single part. that means both letters in every pair have to match. on the other hand, if every pair matches, each pair can be its own part, e.g. 1100 splits into 11 and 00.

so a pair with different letters needs at least one change, and one change is enough to fix it, while a pair with the same letters needs none. the pairs don't affect each other, so we can increment the total number of changes for every pair that's different, and return that after iterating through s. e.g. 1001 has two different pairs, 10 and 01, so it needs 2 changes (e.g. to 1100).

code link to code

class Solution {
public:
    int minChanges(string s) {
        int n{static_cast<int>(s.size())};
        int ans{0};

        for (int i = 0; i < n; i += 2) {
            if (s[i] != s[i+1]) {
                ++ans;
            }
        }

        return ans;
    }
};

complexity link to complexity

  • Time: O(n)
  • Space: O(1)

time taken link to time taken

  • 2 minutes and 3 seconds