Python程序：查找二进制字符串中最多翻转一个0后最长连续1子字符串的长度

假设我们有一个二进制字符串 s。我们最多允许将一个“0”翻转为“1”，我们需要找到最长连续1子字符串的长度。

因此，如果输入类似于 s = "1010110001"，则输出将为 4，因为如果我们将索引 3 处的零翻转，则得到字符串 "1011110001"，这里最长连续1子字符串的长度为 4。

为了解决这个问题，我们将遵循以下步骤：

• n := s 的大小
• ans := 0，ones := 0，left := 0，right := 0
• 当 right < n 时，执行以下操作：
  • 如果 s[right] 等于 "1"，则：
    • ones := ones + 1
  • 当 right - left + 1 - ones > 1 时，执行以下操作：
    • remove := s[left]
    • 如果 remove 等于 "1"，则：
      • ones := ones - 1
    • left := left + 1
  • ans := ans 和 (right - left + 1) 中的最大值
  • right := right + 1
• 返回 ans

示例

让我们看看以下实现以获得更好的理解：

def solve(s):
   n = len(s)
   ans = ones = left = right = 0
   while right < n:
      if s[right] == "1":
         ones += 1
      while right - left + 1 - ones > 1:
         remove = s[left]
         if remove == "1":
            ones -= 1
         left += 1
      ans = max(ans, right - left + 1)
      right += 1
   return ans

s = "1010110001"
print(solve(s))

输入

"1010110001"

输出

4

Arnab Chakraborty

更新于： 2021年10月19日

597 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始