Pythonで各文字がk回以上出現する最長部分文字列の長さを求める方法

問題の概要

ソート済みの文字列 s と整数 k が与えられます。このとき、「すべての文字が少なくとも k 回以上出現する」という条件を満たす最長の部分文字列の長さを求めるのが目的です。

例えば、入力が s = "aabccddeeffghij"、k = 2 の場合を考えてみましょう。このとき最も長い条件を満たす部分文字列は "ccddeeff" であり、c・d・e・f の各文字がそれぞれ2回ずつ出現しています。したがって、答えは 8 となります。

アルゴリズムの考え方

この問題は分割統治法を使うことで効率的に解けます。基本的なアイデアは次のとおりです。

• まず Counter を使って文字列全体の各文字の出現回数を集計します。
• k 回未満しか出現しない文字は、答えとなる部分文字列に含まれないため「区切り文字」として扱います。
• 区切り文字で文字列を分割し、得られた各セグメントに対して同じ処理を再帰的に適用します。
• セグメント内のすべての文字が k 回以上出現していれば、その長さが答えの候補になります。

解決手順

具体的な実装手順は以下のとおりです。

1. 再帰関数 rc() を定義します。引数として文字のリスト lst を受け取ります。
2. c := 各文字とその出現回数を格納するマップ(Counter)
3. acc := 条件を満たす文字を一時的に保持する新しいリスト
4. ans := 0(これまでに見つかった最大長)
5. valid := True(現在のリスト全体が条件を満たすかどうかのフラグ)
6. lst 内の各文字 x について次を繰り返します。
   • c[x] < k の場合(出現回数が k 未満):valid を False にし、ans を ans と rc(acc) の最大値で更新したうえで、acc を空のリストにリセットします。
   • それ以外の場合:x を acc の末尾に追加します。
7. ループ終了後、valid が True なら acc のサイズ(= リスト全体の長さ)を返します。
8. valid が False の場合は、残った acc に対しても rc() を呼び出して ans を更新し、その ans を返します。
9. メイン処理では、文字列 s を1文字ずつのリストに変換して rc() に渡し、その結果を返します。

実装例(Python)

以下が実際のPythonコードです。

from collections import Counter

class Solution:
    def solve(self, s, k):
        def rc(lst):
            c = Counter(lst)
            acc = []
            ans = 0
            valid = True
            for x in lst:
                if c[x] < k:
                    valid = False
                    ans = max(ans, rc(acc))
                    acc = []
                else:
                    acc.append(x)
            if valid:
                return len(acc)
            else:
                ans = max(ans, rc(acc))
                return ans
        return rc(list(s))

ob = Solution()
s = "aabccddeeffghij"
k = 2
print(ob.solve(s, k))

入力

"aabccddeeffghij", 2

出力

8

まとめ

このアルゴリズムでは、条件を満たさない文字(k 回未満の出現)を境に文字列を再帰的に分割していくことで、答えとなる最長部分文字列を効率よく見つけられます。Counter による出現回数の集計と、再帰的な分割統治を組み合わせるのがポイントです。文字列があらかじめソートされている場合でも、同様のアプローチがそのまま適用できます。