サブストリングのゼロの数の2倍がPythonのサブストリングのゼロの数の3倍以下であるサブストリングの長さを見つけるプログラム

文字列と整数kが与えられたと仮定します。文字列はk回繰り返され、別の文字列になります。私たちのタスクは、2 *（部分文字列のゼロの数）<=3 *（部分文字列の1の数）である新しい文字列の部分文字列の長さを見つけることです。

したがって、入力がk =2、input_str ='0101011'の場合、出力は14になります。

文字列の長さは7です。したがって、最初の文字列から作成される新しい文字列は01010110101011です。ここで0の数は6で、1の数は8です。したがって、2 * 6 <=3*8です。したがって、最大のサブストリングは長さ14のストリング全体です。

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

• str_len：=input_strのサイズ
• list_a：=0で初期化されたサイズ（str_len + 1）の新しいリスト
• list_b：=0で初期化されたサイズ（str_len + 1）の新しいリスト
• list_b [0]：=（0、0）を含む新しいペア
• 0からstr_lenの範囲のiの場合、実行
  • list_a [i + 1]：=list_a [i]-3 *（input_str[i]が'1'と同じ場合は1、それ以外の場合は0）+ 2 *（input_str[i]が'0と同じ場合は1 '、それ以外の場合0）
  • list_b [i + 1]：=（list_a [i + 1]、i + 1）で構成される新しいペア
• リストlist_bを並べ替える
• temp_list：=0で初期化されたサイズ（str_len + 1）の新しいリスト
• temp_list [0]：=list_b [0、1]
• 0からstr_lenの範囲のiの場合、実行
  • temp_list [i + 1] =最大（temp_list [i]、list_b [i + 1、1]）
• res：=0
• 0からstr_lenの範囲のiの場合、実行
  • tmp：=list_b [0、0] --list_a [i]
  • list_a [str_len] <=0の場合、
    • a：=k-1
    • tmp + list_a [str_len] * a> 0の場合、
      • 次の反復に進む
  • それ以外の場合、tmp> 0の場合、
    • 次の反復に進む
  • それ以外の場合、
    • a：=最小値（k-1、フロア値（-tmp / list_a [str_len]））
  • v：=a * list_a [str_len] --list_a [i]
  • b：=（並べ替えられた順序を維持しながらペア（-v + 1、0）を挿入できるlist_b内の位置）-1
  • res：=最大（res、temp_list [b] --i + a * str_len）
• return res

例

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

from bisect import bisect_left
def solve(k, input_str):
   str_len = len(input_str)
   list_a = [0] * (str_len + 1)
   list_b = [0] * (str_len + 1)
   list_b[0] = (0, 0)
   for i in range(str_len):
      list_a[i + 1] = list_a[i] - 3 * (input_str[i] == '1') + 2 * (input_str[i] == '0')
      list_b[i + 1] = (list_a[i + 1], i + 1)

   list_b.sort()
   temp_list = [0] * (str_len + 1)
   temp_list[0] = list_b[0][1]
   for i in range(str_len):
      temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])
   res = 0
   for i in range(str_len):
      tmp = list_b[0][0] - list_a[i]
      if list_a[str_len] <= 0:
         a = k - 1
         if tmp + list_a[str_len] * a > 0:
            continue
      elif tmp > 0:
         continue
      else:
         a = min(k - 1, -tmp // list_a[str_len])

      v = a * list_a[str_len] - list_a[i]
      b = bisect_left(list_b, (-v + 1, 0)) - 1
      res = max(res, temp_list[b] - i + a * str_len)
   return res

print(solve(2, '0101011'))

入力

2, '0101011'

出力

14