Pythonで文字列をk回繰り返したとき、0の数×2が1の数×3以下となる最長部分文字列の長さを求める方法

問題概要

文字列と整数 k が与えられます。与えられた文字列を k 回繰り返して連結し、新しい文字列を作成します。この課題では、新しい文字列の中から「2 × (部分文字列に含まれる 0 の個数) ≤ 3 × (部分文字列に含まれる 1 の個数)」という条件を満たす部分文字列のうち、最も長いものの長さを求めます。

たとえば、入力が k = 2、input_str = '0101011' の場合、出力は 14 になります。

元の文字列の長さは 7 なので、繰り返しによって生成される新しい文字列は 01010110101011 です。この文字列には 0 が 6 個、1 が 8 個含まれており、2 × 6 ≤ 3 × 8 が成立します。そのため、条件を満たす最長の部分文字列は文字列全体となり、答えは長さ 14 となります。

解法のアプローチ

この問題は、累積和(プレフィックスサム)と二分探索を組み合わせることで効率的に解けます。各文字に対して「1 が出たら −3、0 が出たら +2」という重みを累積値として記録しておくことで、任意の区間における「2 × 0 の個数 − 3 × 1 の個数」の値を即座に計算できます。

これを解くために、次の手順に従います。

• str_len := 入力文字列 input_str の長さ
• list_a := 長さ (str_len + 1) のリストを 0 で初期化(累積値を格納)
• list_b := 長さ (str_len + 1) のリストを 0 で初期化
• list_b[0] := ペア (0, 0) を設定
• i を 0 から str_len までループ:
  • 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 := 長さ (str_len + 1) のリストを 0 で初期化
• temp_list[0] := list_b[0][1]
• i を 0 から str_len までループ:
  • temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])
• res := 0
• i を 0 から str_len までループ:
  • 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 := min(k − 1, floor(−tmp ÷ list_a[str_len]))
  • v := a × list_a[str_len] − list_a[i]
  • b := (ソート順を維持したまま (−v + 1, 0) を挿入できる list_b 内の位置) − 1
  • res := max(res, temp_list[b] − i + a × str_len)
• 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

アルゴリズムのポイント

この解法の鍵は、条件式「2 × 0 の個数 ≤ 3 × 1 の個数」を「2 × 0 の個数 − 3 × 1 の個数 ≤ 0」に変形し、各位置での累積値を事前に計算しておく点にあります。こうすることで、任意の区間 [i, j] における条件判定を定数時間で行えます。さらに、候補となる位置をソート済みリストとして管理し、二分探索(bisect_left)によって条件を満たす最適な位置を高速に特定することで、文字列を k 回繰り返しても現実的な計算量で答えを求められるようになっています。