Pythonで1文字削除するだけで全文字の出現頻度を同じにできるか判定する方法

小文字のみで構成された文字列 s が与えられたとします。このとき、たった1文字を削除するだけで、すべての文字の出現頻度が等しくなるかどうかを判定する問題を考えます。

例えば、入力が s = "abbc" の場合、出力は True になります。「b」を1つ削除すれば「abc」となり、各文字の出現回数がすべて1回で揃うためです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• まず、文字列 s 内の各文字とその出現回数を対応付けたマップ(辞書)を作成します。
• すべての文字の出現回数がすでに同じであれば、True を返します。
• 次に、文字列内の各文字について以下を試します。
  • その文字の出現回数を1減らす(=1文字削除をシミュレート)
  • この状態ですべての文字の出現回数が同じになれば、True を返します
  • 検証後は元に戻すため、出現回数を1増やします
• どの1文字を削除しても頻度を揃えられなければ、False を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

from collections import defaultdict
def allSame(occurrence):
    counts = list(occurrence.values())
    return all(element == counts[0] for element in counts)
def solve(s):
    occurrence = defaultdict(int)
    for char in s:
        occurrence[char] += 1
    if allSame(occurrence):
        return True
    for char in s:
        occurrence[char] -= 1
        if allSame(occurrence):
            return True
        occurrence[char] += 1
    return False
s = "abbc"
print(solve(s))

入力

"abbc"

出力

True

計算量のポイント

このアルゴリズムでは、各文字の削除を試行するたびに出現回数の一致を再チェックするため、時間計算量は O(n × k) となります(n は文字列長、k は文字種数)。英小文字のように文字種が最大26種と限られている場合、k は定数とみなせるため、実用上は十分高速に動作します。より効率化したい場合は、collections.Counter で頻度の分布を事前に集計し、条件分岐だけで判定する O(n) の実装も可能です。