💬 Discord
Sign In
NeetCode #77LC-1758EasyArrays & Hashing
← Back to All Problems

#77 · #1758 · Minimum Changes To Make Alternating Binary String(生成交替二进制字符串的最少操作数)

📌 Problem Statement & Constraints

Given a binary string s, return the minimum number of changes needed to make it alternating (no two adjacent characters equal). A change flips one character. Constraints: 1 <= s.length <= 10^4.

💡 Core Algorithmic Approaches

  1. There are exactly two alternating patterns of a given length: starting with 0 or starting with 1.
  2. Count how many positions differ from the 0101... pattern; call it cnt.
  3. The other pattern differs at exactly the complementary positions, so its mismatch count is n - cnt.
  4. The answer is min(cnt, n - cnt).

💻 Benchmark Python3 Implementation

class Solution:
    def minOperations(self, s: str) -> int:
        cnt = 0                            # mismatches against the "0101..." pattern
        for i, ch in enumerate(s):
            if int(ch) != i % 2:
                cnt += 1
        return min(cnt, len(s) - cnt)      # the other pattern is the complement

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): a single counter.

⚠️ Interview Pitfalls & Follow-ups

  • Only counting mismatches against one pattern: you must consider both alternating patterns and take the minimum.
  • Constructing both patterns explicitly: unnecessary; the second count is always n - cnt.
  • Counting mismatches against 1010... and forgetting the complement: the same error, expressed differently.
  • Flipping characters and simulating: greedy simulation is O(n^2) and harder to reason about than the direct count.