Pythonでビットの1つのペアを交換した後、最長の1を見つけるプログラム

バイナリ文字列sがあるとします。文字列内の最大1組の文字を入れ替えることができる場合は、連続する最長の1の部分文字列の結果の長さを見つける必要があります。

したがって、入力がs ="1111011111"の場合、s[4]とs[9]を入れ替えて9つの連続した1を取得できるため、出力は9になります。

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

• l：=0、cnt：=0、ans：=0
• 0からsのサイズの範囲のrについては、
  • cnt：=cnt +（s[r]が"0"と同じ場合は1、それ以外の場合は0）
  • cnt> 1の場合、
    • cnt：=cnt-（s [l]が「0」の場合は1、それ以外の場合は0）
    • l：=l + 1
  • ans：=ansの最大値と（r --l + 1）
• 最小のansと1のsの出現を返す

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

例

class Solution:
   def solve(self, s):
      l = 0
      cnt = 0
      ans = 0
      for r in range(len(s)):
         cnt += s[r] == "0"
         if cnt > 1:
            cnt -= s[l] == "0"
            l += 1
         ans = max(ans, r - l + 1)
      return min(ans, s.count("1"))
ob = Solution()
s = "1111011111"
print(ob.solve(s))

入力

"1111011111"

出力

9