Pythonで文字列の全部分文字列に含まれる固有文字の数を合計するプログラム

問題概要

小文字のみで構成された文字列 s が与えられます。s のすべての部分文字列を対象に、それぞれの部分文字列内で重複せず一度だけ現れる文字の個数を数え、その総和を求めます。答えが非常に大きくなる場合は、10^9 + 7 で割った余りを返します。

たとえば、入力が s = "xxy" のとき、出力は 6 になります。各部分文字列と固有文字のカウントは以下のとおりです。

• "x" : 1
• "x" : 1
• "y" : 1
• "xx" : 0(x が重複しているため)
• "xy" : 2
• "xxy" : 1(x が重複しているため)

合計すると 1 + 1 + 1 + 0 + 2 + 1 = 6 となり、これが求める答えです。

解法のポイント

すべての部分文字列を実際に生成して数える方法は、文字列長を n とすると O(n²) 個の部分文字列を扱うことになり、非効率です。そこで視点を変え、「ある位置の文字が、何個の部分文字列において一意な文字として数えられるか」を直接計算します。

位置 i にある文字に注目すると、この文字が部分文字列内で唯一の存在になるのは、部分文字列の開始位置が「直前に同じ文字が出現した位置より後」であり、かつ終了位置が「次に同じ文字が出現する位置より前」である場合です。したがって、この出現位置が答えに貢献する数は次の式で表せます。

(i − 直前の出現位置) × (次の出現位置 − i)

この式をすべての出現位置について足し合わせれば、答えが得られます。

アルゴリズムの手順

• m := 10^9 + 7(剰余演算用の定数)
• prev_seen := 各文字の出現位置の履歴を保持する辞書(初期値は空)
• ans := 0(答えを格納する変数)
• util(i, symbol) という関数を定義する
• prev_seen[symbol] が未登録なら [−1](左端の番兵)で初期化し、リスト prev を取得する
• prev の末尾に現在位置 i を追加する
• prev の要素数が 3 を超えている場合:
  • left := 先頭要素を取り出して削除
  • middle := prev[0]、right := prev[1]
  • cnt := (middle − left) × (right − middle)
  • ans := (ans + cnt) mod m
• s の各インデックス i と文字 symbol について util(i, symbol) を呼び出す
• すべての文字を処理した後、各文字に対して util(len(s), symbol) を呼び出し、文字列の右端を番兵として登録する
• ans を返す

実装例(Python)

class Solution:
    def solve(self, s):
        m = 10 ** 9 + 7
        prev_seen = {}
        ans = 0
        def util(i, symbol):
            nonlocal ans
            prev = prev_seen.setdefault(symbol, [−1])
            prev.append(i)
            if len(prev) > 2:
                left = prev.pop(0)
                middle, right = prev
                cnt = (middle − left) * (right − middle)
                ans = (ans + cnt) % m
        for i, symbol in enumerate(s):
            util(i, symbol)
        for symbol in prev_seen:
            util(len(s), symbol)
        return ans

ob = Solution()
s = "xxy"
print(ob.solve(s))

入力

xxy

出力

6

計算量の目安

各文字の出現をそれぞれ定数回ずつ処理するだけでよいため、時間計算量は文字列長を n としてほぼ O(n) に抑えられます。部分文字列を全列挙する素朴な手法(O(n²)〜O(n³))と比べ、長い文字列でも高速に動作するのが大きな利点です。