Pythonで2つの文字列をアナグラムのペアになるように分割するプログラム

同じ長さを持つ2つの空でない文字列 s と t が与えられたとします。これらを部分文字列に分割し、s と t の各ペアが同じサイズで、互いにアナグラム（並べ替え語）となるようにします。そのうえで、s と t を最大回数カットできるような切り分け位置（インデックス）を求めます。条件を満たす結果が存在しない場合は、空のリストを返します。

例えば、入力が s = "bowcattiger"、t = "owbactietgr" の場合、出力は [0, 3, 5, 6, 10] となります。これは、文字列を5つの区間に分割でき、それぞれの対応する部分文字列が互いにアナグラムになっているためです。具体的には、s = ["bow", "ca", "t", "tige", "r"]、t = ["owb", "ac", "t", "ietg", "r"] と分割されます。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• intervals := 新しいリストを作成する
• cs := 文字列 s に含まれる各文字とその出現頻度を記録したマップ（Counter）を作成する
• ct := 文字列 t に含まれる各文字とその出現頻度を記録したマップ（Counter）を作成する
• もし cs と ct が等しくない場合（全体としてアナグラムになっていない場合）は、
  • 空のリストを返す
• x を s の長さ - 1 から 0 まで逆順にループさせる：
  • cs[s[x]] の値を 1 減らす
  • ct[t[x]] の値を 1 減らす
  • もしこの時点で cs と ct が等しければ、
    • x を intervals の末尾に追加する
• intervals をソートして返す

このアルゴリズムのポイントは、右端から順に文字を「取り除いて」いき、そのたびに残りの部分の文字頻度マップが一致するかどうかを確認することです。一致した時点が、有効な切り分け境界となります。Counter 同士の比較は O(1) 相当で行えるため、全体の計算量は O(n) 程度で効率的に処理できます。

理解を深めるために、以下の実装例をご覧ください。

実装例

from collections import Counter
class Solution:
    def solve(self, a, b):
        intervals = []
        ca = Counter(a)
        cb = Counter(b)
        if ca != cb:
            return []
        for x in reversed(range(len(a))):
            ca[a[x]] -= 1
            cb[b[x]] -= 1
            if ca == cb:
                intervals.append(x)
        return sorted(intervals)
ob = Solution()
s = "bowcattiger"
t = "owbactietgr"
print(ob.solve(s, t))

入力

"bowcattiger", "owbactietgr"

出力

[0, 3, 5, 6, 10]