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
- There are exactly two alternating patterns of a given length: starting with
0or starting with1. - Count how many positions differ from the
0101...pattern; call itcnt. - The other pattern differs at exactly the complementary positions, so its mismatch count is
n - cnt. - 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.
🧩 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)