Pythonで解く「特別に同等な文字列」のグループ数カウント問題

問題概要

文字列の配列 A が与えられます。文字列 S に対する「1回の操作」とは、S の偶数番目(0始まり)のインデックスにある2文字同士を入れ替える、または奇数番目のインデックスにある2文字同士を入れ替えることを意味します。

任意の回数だけ操作を繰り返した結果、S が T と一致させられる場合、2つの文字列 S と T は「特別に同等(special-equivalent)」であると定義されます。たとえば、S = "zzxy" と T = "xyzz" は特別に同等です。S[0] と S[2] を入れ替えて "xzzy" とし、続けて S[1] と S[3] を入れ替えることで "xyzz" を作れるためです。

配列 A から選ばれる「特別同等文字列のグループ」とは、次の条件を満たす空でない部分集合のことです。

• グループ内のどの文字列ペアも互いに特別に同等である
• グループは最大サイズである(グループ外に、グループ内のすべての文字列と特別に同等な文字列 S が存在しない)

このとき、配列 A から作れる特別同等文字列のグループの個数を求めます。たとえば入力が ["abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"] の場合、出力は 3 になります。1つ目のグループは ["abcd", "cdab", "cbad"] で、これらはすべて互いに特別に同等であり、ほかの文字列はこのグループと特別に同等ではありません。残りの2つのグループは ["xyzz", "zzxy"] と ["zzyx"] です。

解法の考え方

重要なポイントは、偶数インデックスの文字同士は自由に入れ替え可能で、奇数インデックスの文字も同様に自由に入れ替え可能という点です。つまり次のことが成り立ちます。

• 2つの文字列が特別に同等 ⟺ 偶数位置の文字の構成(出現頻度)が等しく、かつ奇数位置の文字の構成も等しい

そこで、「偶数位置の文字をソートしたもの + 奇数位置の文字をソートしたもの」を各文字列の正規形(シグネチャ)として採用すると、同じシグネチャを持つ文字列どうしが必ず同じグループに属します。あとはユニークなシグネチャの種類数を数えるだけで答えが得られます。

手順

• 空のセット codes を用意する
• A 内の各 word について:
  • 偶数位置の文字をソートした文字列と、奇数位置の文字をソートした文字列を連結して code を作る
  • code を codes に追加する
• codes のサイズを返す

実装例(Python)

class Solution:
    def numSpecialEquivGroups(self, A):
        codes = set()
        for word in A:
            code = ''.join(sorted(word[::2])) + ''.join(sorted(word[1::2]))
            codes.add(code)
        return len(codes)

ob = Solution()
print(ob.numSpecialEquivGroups(["abcd","cdab","cbad","xyzz","zzxy","zzyx"]))

入力

["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

出力

3

計算量

文字列の総数を N、各文字列の長さを L とすると、各文字列ごとに長さ L/2 の部分文字列を2回ソートするため O(L log L) が必要で、全体の時間計算量は O(N × L log L) になります。空間計算量は保存するシグネチャ分の O(N × L) です。スライス表記 word[::2](偶数インデックス)と word[1::2](奇数インデックス)を使うことで、簡潔に正規形を構築できるのが Python らしいポイントです。