⚡Flashcard Drill➔
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.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems

中文速览与面试要点

生成交替二进制字符串的最少操作数

给你一个仅由字符 0 和 1 组成的字符串 s。在一步操作中,你可以将 s 中的任意一个字符反转(0 变成 1,1 变成 0)。返回使 s 变成 交替字符串 所需要的最少操作数。交替字符串的定义:不存在两个相邻字符相同,即形如 0101... 或 1010...。约束:1 ≤ s.length ≤ 10^4;s 仅由 0 和 1 组成。

核心要点

  • 两种目标模式(核心洞察) :交替字符串只有两种可能——以 0 开头的 0101... 和以 1 开头的 1010... 。
  • 分别计算代价 :对目标模式 0101... ,位置 i 的期望字符是 i % 2 (0 对应偶数下标)。统计与期望不符的位置数 d1,则另一种模式的代价为 n - d1 (因为两种模式在每个位置恰好互补)。
  • 答案 = min(d1, n - d1) :取两种模式中代价较小者。
  • 为什么只需算一种 :两种目标模式在每个位置字符相反,因此「不符个数」之和恒为 n,无需重复扫描。

常见陷阱

  • 只考虑一种目标模式 :只算 0101... 的代价会漏掉 1010... 可能更优的情况(如 s = "10" 时后者代价为 0)。
  • 重复扫描两次 :分别计算两种模式的代价是 O(2n),虽然复杂度相同,但用 n - diff 的互补关系更优雅。
  • 比较时用字符而非整数 : c != str(i % 2) 也可行,但 int(c) != i % 2 更直观。

参考实现

class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)
        # 目标模式一:偶数下标为 0、奇数下标为 1(即 i % 2)
        diff = sum(1 for i, c in enumerate(s) if int(c) != i % 2)
        return min(diff, n - diff)