Pythonで1回0フリップした後、バイナリ文字列で1が含まれる最長の部分文字列の長さを検索するプログラム

バイナリ文字列sがあるとします。最大で1つの「0」から「1」に反転できます。連続する最長の1の部分文字列の長さを見つける必要があります。

したがって、入力がs ="1010110001"の場合、出力は4になります。たとえば、インデックス3にあるゼロを反転すると、文字列 "1011110001"が得られます。ここで、1の最長の部分文字列の長さは4です。 。

これを解決するには、次の手順に従います-

• n：=sのサイズ
• ans：=0、ones：=0、left：=0、right：=0
• 正しい
• s[right]が"1"と同じ場合、
  • ones：=ones + 1
• 右-左+1-もの>1、実行
  • 削除：=s[左]
  • removeが「1」と同じ場合、
    • ones：=ones-1
  • 左：=左+ 1
• ans：=ansの最大値と（右-左+ 1）
• 右：=右+1

例

理解を深めるために、次の実装を見てみましょう-

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