【Python】文字列を高々K種類の異なる文字にするために必要な最小の変更回数を求めるプログラム

小文字のアルファベットのみで構成された文字列 s と整数 k が与えられたとき、結果として得られる文字列が「高々 k 種類の異なる文字」しか含まないようにするために必要な最小の変更回数を求めます。ここでいう「変更」とは、1文字を別の任意の文字に置き換える操作のことです。

たとえば、入力が s = "wxxyyzzxx"、k = 3 の場合、出力は 1 になります。これは、文字 "w" を x・y・z のいずれか1文字に置き換えるだけで、異なる文字の種類を3種類（x、y、z）にできるからです。

解法のアプローチ

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

• まず、文字列 s 内の各文字の出現頻度をカウントしたマップ count を作成します
• 次に、出現頻度の値を昇順にソートしたリスト sv を作成します
• 答えとなる変数 ans を 0 で初期化します
• i を 0 から (文字の種類数 − k − 1) までループさせ、ans に sv[i] を加算していきます
• 最後に ans を返します

考え方のポイント

異なる文字の種類数を k 以下に減らすには、余分な文字種をすべて別の文字へ書き換える必要があります。このとき、出現回数が少ない文字から順に置き換えていくことで、必要な変更回数を最小化できます。そのため、頻度を昇順にソートし、頻度の小さい方から (文字の種類数 − k) 個分の合計を求めれば、それが答えになります。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

from collections import Counter
class Solution:
    def solve(self, s, k):
        count = Counter(s)
        sv = sorted(count.values())
        ans = 0
        for i in range(len(count) - k):
            ans += sv[i]
        return ans

ob = Solution()
s = "wxxyyzzxx"
k = 3
print(ob.solve(s, k))

入力

"wxxyyzzxx",3

出力

1