Pythonで「A」と「B」の使用数制限内に生成できる文字列の最大数をカウントするプログラム

それぞれの文字列が「A」と「B」の2種類の文字だけで構成された文字列のリストがあるとします。ここに、2つの整数値 a と b が与えられます。求めたいのは、生成できる文字列の最大数です。ただし、「A」は合計で最大 a 個まで、「B」は合計で最大 b 個までしか使用できず、一度使った文字を再利用することはできません。

たとえば、入力が strings = ["AAABB", "AABB", "AA", "BB"]、a = 4、b = 2 の場合、出力は 2 になります。「A」を4個、「B」を2個消費して ["AABB", "AA"] の2つの文字列を選ぶことができるためです。

解法の考え方

この問題はナップサック問題に似た構造を持っており、動的計画法(DP)を使って効率的に解くことができます。各状態を「残っているAの個数とBの個数の組み合わせ」として辞書で管理し、その状態からこれまでに選んだ文字列の最大数を値として記録していきます。具体的な手順は以下の通りです。

• pairs := 新しい空のリストを作成する
• strings 内の各文字列 w について、次の処理を行う
  • A := w に含まれる「A」の個数
  • B := w の長さから A を引いた値(「B」の個数)
  • ペア (A, B) を pairs の末尾に追加する
• ans := キー (a, b) に値 0 を持つマップ(辞書)として初期化する
• pairs 内の各ペア (A, B) について、次の処理を行う
  • temp := ans のコピーである新しいマップを作成する
  • ans 内の各キー (temp_a, temp_b) とその値 wc について、次の処理を行う
    • もし temp_a >= A かつ temp_b >= B であれば、次の処理を行う
      • rem := ペア (temp_a - A, temp_b - B)
      • temp[rem] := temp[rem](rem が存在しない場合は 0)と (wc + 1) のうち大きい方
  • ans := temp と更新する

このアルゴリズムでは、辞書 ans のキーが「残りのA・Bの個数」、値が「その状態に至るまでに選択した文字列の数」を表します。各文字列を処理するたびに、既存のすべての状態に対してその文字列を追加できるかを確認し、追加できる場合は残り個数を減らした新しい状態を記録します。最終的に、いずれかの状態で達成できる文字列数の最大値が答えとなります。

理解を深めるために、以下の実装例を見てみましょう。

実装例

class Solution:
    def solve(self, strings, a, b):
        pairs = []
        for w in strings:
            A = w.count("A")
            B = len(w) - A
            pairs.append((A, B))
        ans = {(a, b): 0}
        for A, B in pairs:
            temp = dict(ans)
            for (temp_a, temp_b), wc in ans.items():
                if temp_a >= A and temp_b >= B:
                    rem = (temp_a - A, temp_b - B)
                    temp[rem] = max(temp.get(rem, 0), wc + 1)
            ans = temp
        return max(ans.values())

ob = Solution()
strings = ["AAABB", "AABB", "AA", "BB"]
a = 4
b = 2
print(ob.solve(strings, a, b))

入力

["AAABB", "AABB", "AA", "BB"], 4, 2

出力

2