Pythonで文字列内に複数回出現する長さkの部分文字列の個数をカウントする方法

文字列 s と整数 k が与えられたとき、s の中に2回以上出現する長さ k の部分文字列がいくつあるかを求める問題を考えてみましょう。

たとえば、入力が s = "xxxyyy"、k = 2 の場合、出力は 2 になります。これは「xx」と「yy」という2つの部分文字列が、それぞれ複数回出現しているためです。

解決のアプローチ

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

• seen := 空のリストを用意する
• i を 0 から (s の長さ - k) まで繰り返す:
  • t := s のインデックス i から i + k - 1 までの部分文字列
  • t を seen の末尾に追加する
• mp := seen 内の各要素とその出現回数を記録したマップを作成する
• mp の中で出現回数が 1 より多い要素の個数の合計を返す

つまり、すべての長さ k の部分文字列をスライドしながら抽出し、Python標準ライブラリの collections.Counter を使って出現回数を集計するのがポイントです。

実装例

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

class Solution:
    def solve(self, s, k):
        from collections import Counter
        seen = []
        for i in range(len(s) - k + 1):
            t = s[i : i + k]
            seen.append(t)
        s = Counter(seen)
        return sum(1 for x in s.values() if x > 1)

ob = Solution()
print(ob.solve("xxxyyy", 2))

コードの解説

• range(len(s) - k + 1): 長さ k の部分文字列を取り出せる開始位置の範囲を生成します。文字列の長さが n のとき、長さ k の部分文字列は最大 n - k + 1 個存在します。
• s[i : i + k]: スライス構文により、位置 i から始まる長さ k の部分文字列を取得します。
• Counter(seen): リスト内の各部分文字列の出現回数を辞書形式で集計します。
• sum(1 for x in s.values() if x > 1): 出現回数が 2 回以上の部分文字列だけをカウントして合計します。

入力

"xxxyyy", 2

出力

2

このように、Counter を活用することで、シンプルかつ効率的に重複する部分文字列を数えることができます。計算量は O(n・k)（n は文字列の長さ）となり、実用的な範囲で十分高速に動作します。