Pythonで各文字の出現頻度を一意にするために必要な最小削除数を求めるプログラム

問題の概要

文字列 s が与えられます。s に含まれる異なる2つの文字が同じ出現頻度を持たないとき、s は「良い文字列(good string)」であると定義します。ここでの課題は、s を良い文字列に変換するために削除が必要な文字の最小数を求めることです。

例えば、入力が s = "ssstttuu" の場合、答えは 2 になります。まず 't' を1つ削除すると、's' が3個、't' が2個、'u' が2個となります。このままでは 't' と 'u' の頻度が重複しているため、さらに 't' または 'u' のどちらかを1つ削除すると、すべての頻度が一意になり、良い文字列が完成します。

解決のための手順

この問題を解くには、以下の手順に従います。

• val := 文字列 s の各文字の出現頻度を格納する新しいマップ(Counter)を作成
• res := 0(削除回数を記録するカウンタ)
• numlist := val から取り出したすべての頻度値を昇順にソートしたリストを作成
• i を 0 から numlist のサイズ - 2 まで繰り返す
  • numlist[i] が 0 以外で、numlist[i] と numlist[i+1] が等しい場合
    • numlist[i] := numlist[i] - 1
    • res := res + 1
    • k := i - 1、m := i とする
    • numlist[m] が 0 以外で numlist[m] と numlist[k] が等しい間、次を繰り返す
      • numlist[k] := numlist[k] - 1
      • k := k - 1、m := m - 1
      • res := res + 1
• res を返す

実装例(Python)

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

from collections import Counter
def solve(s):
    val = Counter(s)
    res = 0
    numlist = sorted([i for i in val.values()])
    for i in range(len(numlist)-1):
        if numlist[i] and numlist[i] == numlist[i+1]:
            numlist[i] -= 1
            res += 1
            k = i-1
            m = i
            while numlist[m] and numlist[m] == numlist[k]:
                numlist[k] -= 1
                k -= 1
                m -= 1
                res += 1

    return res

s = "ssstttuu"
print(solve(s))

入力

"ssstttuu"

出力

2

アルゴリズムのポイント

頻度のリストを昇順にソートして隣接要素同士を比較することで、重複している頻度を効率的に検出できます。重複が見つかった場合は、小さい方の頻度を1減らし、その変更によってさらに左側の要素との重複が新たに発生しないかを while ループで連鎖的に確認します。これにより、頻度の調整による二次的な衝突も漏れなく処理できます。計算量はソート部分が支配的となり、O(n log n) で文字列の長さ n に対して十分高速に動作します。