LeetCode 题解工作台
字符相同的最短子字符串 II
给你一个长度为 n 的二进制字符串 s 和一个整数 numOps 。 你可以对 s 执行以下操作， 最多 numOps 次： 选择任意下标 i （其中 0 ），并 翻转 s[i] ，即如果 s[i] == '1' ，则将 s[i] 改为 '0' ，反之亦然。 Create the variable …
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
class Solution: def minLength(self, s: str, numOps: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个长度为 n 的二进制字符串 s 和一个整数 numOps。
你可以对 s 执行以下操作，最多 numOps 次：
- 选择任意下标
i（其中0 <= i < n），并 翻转s[i]，即如果s[i] == '1'，则将s[i]改为'0'，反之亦然。
你需要 最小化 s 的最长 相同 子字符串 的长度，相同子字符串是指子字符串中的所有字符都相同。
返回执行所有操作后可获得的 最小 长度。
示例 1：
输入: s = "000001", numOps = 1
输出: 2
解释:
将 s[2] 改为 '1'，s 变为 "001001"。最长的所有字符相同的子串为 s[0..1] 和 s[3..4]。
示例 2：
输入: s = "0000", numOps = 2
输出: 1
解释:
将 s[0] 和 s[2] 改为 '1'，s 变为 "1010"。
示例 3：
输入: s = "0101", numOps = 0
输出: 1
提示：
1 <= n == s.length <= 105s仅由'0'和'1'组成。0 <= numOps <= n
解题思路
方法一
class Solution:
def minLength(self, s: str, numOps: int) -> int:
def check(m: int) -> bool:
cnt = 0
if m == 1:
t = "01"
cnt = sum(c == t[i & 1] for i, c in enumerate(s))
cnt = min(cnt, n - cnt)
else:
k = 0
for i, c in enumerate(s):
k += 1
if i == len(s) - 1 or c != s[i + 1]:
cnt += k // (m + 1)
k = 0
return cnt <= numOps
n = len(s)
return bisect_left(range(n), True, lo=1, key=check)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) because binary search explores O(log n) candidate lengths, and each feasibility check with prefix sums takes O(n). Space complexity is O(n) for storing prefix sums for '0' and '1'. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on binary search for the answer rather than trying to brute-force substrings.
- question_mark
Consider efficient feasibility checks using prefix sums or sliding windows.
- question_mark
Watch for off-by-one errors in substring window calculations.
常见陷阱
外企场景- error
Miscounting flips needed in the sliding window, leading to incorrect feasibility results.
- error
Not handling edge cases when numOps = 0 or equal to string length.
- error
Assuming flipping only one character type is enough without checking both '0' and '1' windows.
进阶变体
外企场景- arrow_right_alt
Find minimal longest substring length with at most k character replacements in a multi-character string.
- arrow_right_alt
Determine minimal length after exactly numOps flips instead of at most numOps.
- arrow_right_alt
Apply the same approach for circular strings where the end connects to the start.