LeetCode 题解工作台
字符相同的最短子字符串 I
给你一个长度为 n 的二进制字符串 s 和一个整数 numOps 。 你可以对 s 执行以下操作， 最多 numOps 次： 选择任意下标 i （其中 0 ），并 翻转 s[i] ，即如果 s[i] == '1' ，则将 s[i] 改为 '0' ，反之亦然。 Create the variable …
3
题型
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 <= 1000s仅由'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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a clear understanding of binary search and sliding window techniques.
- question_mark
Evaluate the ability to optimize the approach with prefix sums or similar techniques.
- question_mark
Check if the candidate can adapt their solution based on the constraints, particularly with larger strings.
常见陷阱
外企场景- error
Failing to implement binary search correctly over the answer space.
- error
Not optimizing the sliding window check for each candidate substring length.
- error
Mismanaging the number of allowed operations, leading to incorrect checks or results.
进阶变体
外企场景- arrow_right_alt
Increase the string size n to test scalability of the solution.
- arrow_right_alt
Add constraints on numOps to limit the number of changes even further.
- arrow_right_alt
Consider different initial configurations of the binary string, such as alternating or uniform strings.