LeetCode Entry

2914. Minimum Number of Changes to Make Binary String Beautiful

05.11.2024 medium 2024 kotlin rust

Min changes to make even-sized 0 and 1

2914. Minimum Number of Changes to Make Binary String Beautiful medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/791

Problem TLDR

Min changes to make even-sized 0 and 1 #medium

Intuition

Observing some examples:


    // 111011
    // 111111 -> 1
    // 110011 -> 1

It is clear that it doesn’t matter which bits we change 0->1 or 1->0. So, the simplest solution is to just count continuous zeros and ones and greedily fix odds.

Something like this:

        while (++i < s.length) {
            while (i < s.length && s[i] == s[j]) i++
            res += (i - j) % 2
            j = i - (i - j) % 2
        }

The cleverer solution comes from the idea: if all substrings are even-sized, they are split at even positions. That means we can scan 2-sized chunks and find all the incorrect splits c[0] != c[1].

Approach

  • let’s do code golf

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun minChanges(s: String) =
        s.chunked(2).count { it[0] != it[1] }



    pub fn min_changes(s: String) -> i32 {
        s.as_bytes().chunks(2).map(|c| (c[0] != c[1]) as i32).sum()
    }



    int minChanges(string s) {
        int cnt = 0;
        for (int i = 0; i < s.size(); i += 2)
            cnt += (s[i] ^ s[i + 1]) & 1;
        return cnt;
    }