Problem

You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

Return theminimum number of operations needed to make s alternating.

Examples

Example 1

1
2
3

Input: s = "0100"
Output: 1
Explanation: If you change the last character to '1', s will be "0101", which is alternating.

Example 2

1
2
3

Input: s = "10"
Output: 0
Explanation: s is already alternating.

Example 3

1
2
3

Input: s = "1111"
Output: 2
Explanation: You need two operations to reach "0101" or "1010".

Constraints

  • 1 <= s.length <= 10^4
  • s[i] is either '0' or '1'.

Solution

Method 1 – Greedy Pattern Matching

Intuition

There are only two possible alternating strings of the same length: one starting with ‘0’ (“010101…”) and one starting with ‘1’ (“101010…”). By comparing the input string to both patterns, we can count the number of changes needed for each and take the minimum.

Approach

  1. Generate two alternating patterns of the same length as s: one starting with ‘0’, one with ‘1’.
  2. For each character in s, compare it to both patterns and count mismatches.
  3. The answer is the minimum of the two mismatch counts.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minOperations(string s) {
        int cnt0 = 0, cnt1 = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != (i % 2 == 0 ? '0' : '1')) cnt0++;
            if (s[i] != (i % 2 == 0 ? '1' : '0')) cnt1++;
        }
        return min(cnt0, cnt1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func minOperations(s string) int {
    cnt0, cnt1 := 0, 0
    for i := 0; i < len(s); i++ {
        if s[i] != byte('0'+byte(i%2)) {
            cnt0++
        }
        if s[i] != byte('1'-byte(i%2)) {
            cnt1++
        }
    }
    if cnt0 < cnt1 {
        return cnt0
    }
    return cnt1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minOperations(String s) {
        int cnt0 = 0, cnt1 = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != (i % 2 == 0 ? '0' : '1')) cnt0++;
            if (s.charAt(i) != (i % 2 == 0 ? '1' : '0')) cnt1++;
        }
        return Math.min(cnt0, cnt1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minOperations(s: String): Int {
        var cnt0 = 0
        var cnt1 = 0
        for (i in s.indices) {
            if (s[i] != if (i % 2 == 0) '0' else '1') cnt0++
            if (s[i] != if (i % 2 == 0) '1' else '0') cnt1++
        }
        return minOf(cnt0, cnt1)
    }
}
1
2
3
4
5
6
7
8

def min_operations(s: str) -> int:
    cnt0, cnt1 = 0, 0
    for i, ch in enumerate(s):
        if ch != ('0' if i % 2 == 0 else '1'):
            cnt0 += 1
        if ch != ('1' if i % 2 == 0 else '0'):
            cnt1 += 1
    return min(cnt0, cnt1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn min_operations(s: String) -> i32 {
        let (mut cnt0, mut cnt1) = (0, 0);
        for (i, ch) in s.chars().enumerate() {
            if ch != if i % 2 == 0 { '0' } else { '1' } { cnt0 += 1; }
            if ch != if i % 2 == 0 { '1' } else { '0' } { cnt1 += 1; }
        }
        cnt0.min(cnt1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    minOperations(s: string): number {
        let cnt0 = 0, cnt1 = 0;
        for (let i = 0; i < s.length; i++) {
            if (s[i] !== (i % 2 === 0 ? '0' : '1')) cnt0++;
            if (s[i] !== (i % 2 === 0 ? '1' : '0')) cnt1++;
        }
        return Math.min(cnt0, cnt1);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, as we scan the string once.
  • 🧺 Space complexity: O(1), only counters are used.