Pythonで数値文字列がペア1つとトリプル複数個に並べ替え可能か判定する方法

問題概要

数値文字列 s が与えられます。この文字列を並べ替えて、「同じ数字2つからなるペア」をちょうど1つ作り、残りの部分をすべて「同じ数字3つからなるトリプル」に分割できるかどうかを判定します。

例えば、入力が s = "21133123" の場合、出力は True になります。「2」が2つあるので「22」というペアを作ることができ、残りの「111」「333」がそれぞれトリプルとして成立するためです。

解き方のアプローチ

この問題は、次の手順で解決できます。

1. 文字列に含まれる各数字の出現回数をカウントする(Counter を使用)。
2. 各数字 k について、そのカウントから2を減らして「ペアを作る」状況をシミュレートする。
3. すべての数字の残りカウントが3で割り切れる場合、True を返す。
4. 条件を満たさなければ、カウントに2を戻して次の数字を試す。
5. どの数字をペアにしても成立しない場合は False を返す。

実装例(Python)

以下のコードで実際の動作を確認できます。

from collections import Counter

def solve(s):
    d = Counter(s)
    for k in d:
        d[k] -= 2
        if all(d[i] % 3 == 0 for i in d):
            return True
        d[k] += 2
    return False

s = "21133123"
print(solve(s))

入力

"21133123"

出力

True

計算量の分析

時間計算量は O(n × k) となります(n は文字列の長さ、k は異なる数字の種類数)。ペアの候補となる各数字について、全数字のカウントを再確認する必要があるためです。空間計算量は O(k) で、カウンターの格納に必要な分だけです。

まとめ

この問題のポイントは、「ペアに使う数字を1つ選び、残りがすべて3の倍数になるか」を全パターン試すシンプルな全探索アプローチです。Counter による頻度管理と all() 関数を組み合わせることで、簡潔かつ読みやすいコードで実装できます。