Problem

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

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3

Input: s = "0000"
Output: 0
Explanation: We don't need to make any changes as the string "0000" is beautiful already.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Count consecutive characters

Here is the approach:

  • Iterate through s and compare each element to the last seen element.
  • If they are equal, increment the counter.
  • If they are different, check if the counter is even or odd.
    • If it’s even, reset the counter to 1;
    • if odd, reset the counter to 0 and increment the answer (indicating a change is needed as the current element should match the previous one).
  • Finally, update last seen to the current element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int minChanges(String s) {
        int changes = 0;
        char currChar = s.charAt(0);
        int count = 0;

        for (char ch : s.toCharArray()) {
            if (ch == currChar) {
                count++;
                continue;
            }
            if (count % 2 == 1) {
                changes++;
                count = 0;
            } else {
                count = 1;
            }
            currChar = ch;
        }

        return changes;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minChanges(self, s: str) -> int:
        changes: int = 0
        currChar: str = s[0]
        count: int = 0

        for ch in s:
            if ch == currChar:
                count += 1
                continue
            if count % 2 == 1:
                changes += 1
                count = 0
            else:
                count = 1
            lastSeen = ch  # Update lastSeen to the new character

        return changes

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string
  • 🧺 Space complexity: O(1)

Method 2 - Just compare 2 adjacent characters

Since the string length is even, split it into groups of two and check if each group has characters such that either all are 0s or all 1s.

Here is the approach:

  1. Initialise a counter ans to track the required changes.
  2. Iterate through the string, inspecting each adjacent pair by increasing the index by 2.
  3. Increment ans if the characters in the pair differ.
  4. Return ans as the minimum number of changes needed to make the string “beautiful.”

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int minChanges(String s) {
        int changes = 0;
        
        for (int i = 0; i < s.length(); i += 2) {
            if (s.charAt(i) != s.charAt(i + 1)) {
                changes++;
            }
        }

        return changes;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minChanges(self, s: str) -> int:
        changes: int = 0
        n: int = len(s)
        
        for i in range(0, n, 2):
            if i + 1 < n and s[i] != s[i + 1]:
                changes += 1

        return changes

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)