Pythonで文字列の全部分文字列の「美しさ」の合計を求めるプログラム

問題の概要

文字列 s が与えられたとき、そのすべての部分文字列について「美しさ（beauty）」を計算し、その合計を求めることを考えます。

ここでいう文字列の「美しさ」とは、最も出現頻度の高い文字と最も出現頻度の低い文字の出現回数の差のことです。たとえば文字列 "abaacc" の場合、最頻文字は a（3回）、最稀文字は b や c（各1回）なので、美しさは 3 − 1 = 2 となります。

具体例

入力が s = "xxyzy" の場合、出力は 5 になります。これは、美しさが 0 以外になる部分文字列が ["xxy", "xxyz", "xxyzy", "xyzy", "yzy"] の5つであり、それぞれの美しさが 1 だからです。

解法のアプローチ

この問題は、すべての部分文字列を全探索する素直な方法で解くことができます。手順は以下のとおりです。

• 結果を格納する変数 res を 0 で初期化する。
• 開始位置 i を 0 から文字列長 − 1 まで順に動かす。
• 終了位置 j を i + 2 から文字列長 − 1 まで順に動かす（長さ1・2の部分文字列は美しさが必ず 0 になるためスキップできる）。
• s[i..j] の各文字の出現頻度をマップとしてカウントする。
• 頻度の最大値から最小値を引いた値を res に加算する。
• すべての組み合わせを処理し終えたら res を返す。

Pythonでの実装例

以下のコードでは、標準ライブラリの collections.Counter を使って文字の出現頻度を簡単に集計しています。

from collections import Counter

def solve(s):
    res = 0
    for i in range(len(s)):
        for j in range(i + 2, len(s)):
            c = Counter(s[i:j + 1])
            v = c.values()
            res += (max(v) - min(v))
    return res

s = "xxyzy"
print(solve(s))

入力

"xxyzy"

出力

5

計算量のポイント

この実装では、開始位置と終了位置の組み合わせが O(n²) 通りあり、さらにそれぞれの部分文字列に対して頻度カウントを行うため O(n) の処理が必要になります。したがって全体の時間計算量は O(n³) です。

文字列が短いうちは十分実用的ですが、入力が長くなる場合は、開始位置 i を固定したまま終了位置を1文字ずつ伸ばしながら Counter を逐次更新する方式に書き換えることで、計算量を O(n²) まで改善できます。