Pythonで最長アナグラム部分列の長さを求めるプログラム

問題の概要

小文字のみで構成された2つの文字列 S と T が与えられたとき、「最も長いアナグラム部分列」の長さを求めます。ここでアナグラム部分列とは、両方の文字列に共通して含まれる文字を組み合わせて作れる、同じ文字構成を持つ部分列のことです。

例えば、S = "helloworld"、T = "hellorld" の場合、答えは 8 になります。これは、両方の文字列で共有できる文字（h ×1、e ×1、l ×3、o ×1、r ×1、d ×1）の合計が8文字であるためです。

解法のアプローチ

この問題は、各文字列における文字の出現回数を数え、その最小値を合計することで効率的に解けます。手順は以下の通りです。

1. 文字列 S の各文字の出現回数を記録する辞書 c を作成します。
2. 文字列 T の各文字の出現回数を記録する辞書 d を作成します。
3. c 内の各文字 ch について、d にも存在する場合は min(c[ch], d[ch]) を結果に加算します。
4. 最終的な合計値を返します。

この方法により、共通して使える文字数の最大値が求まります。

実装例

class Solution:
    def solve(self, a, b):
        c, d = {}, {}
        for i in range(len(a)):
            if a[i] in c:
                c[a[i]] += 1
            else:
                c[a[i]] = 1
        for i in range(len(b)):
            if b[i] in d:
                d[b[i]] += 1
            else:
                d[b[i]] = 1
        res = 0
        for ch in c:
            if d.get(ch, 0) > 0:
                res += min(c[ch], d[ch])
        return res

ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))

入力

S = "helloworld", T = "hellorld"

出力

8

補足：collections.Counter を使った簡潔な実装

Pythonでは標準ライブラリの collections.Counter を使うと、文字数のカウント処理をより簡潔に書けます。

from collections import Counter

def longest_anagram_subsequence(a, b):
    ca, cb = Counter(a), Counter(b)
    return sum((ca & cb).values())

S = "helloworld"
T = "hellorld"
print(longest_anagram_subsequence(S, T))  # 出力: 8

Counter 同士の & 演算子は、各キーについて最小値を取るため、まさにこの問題に適しています。

計算量

• 時間計算量： O(n + m) — n、m はそれぞれ文字列 S、T の長さです。
• 空間計算量： O(1) — 対象が英小文字26種類に限られるため、辞書のサイズは一定です。