Groups of Special-Equivalent Strings (กลุ่มสตริงเทียบเท่าพิเศษ) ใน Python

โจทย์: สตริง S และ T เป็น "Special-Equivalent" ถ้าสลับตัวอักษรตำแหน่งคู่ (Even indices) กันได้ หรือสลับตำแหน่งคี่ (Odd indices) กันได้ แล้วเท่ากัน หาจำนวนกลุ่ม Special-Equivalent จาก Array A

Input/Output

Input:  ["abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"]
Output: 3
# Group 1: ["abcd", "cdab", "cbad"] (Even: ac/bd, Odd: bd/ac สลับได้)
# Group 2: ["xyzz", "zzxy"] (Even: xz, Odd: yz)
# Group 3: ["zzyx"] (Even: zy, Odd: zx)

ข้อสังเกตสำคัญ

สตริง 2 ตัว Special-Equivalent ก็ต่อเมื่อ Multiset ของ Even indices เหมือนกัน AND Multiset ของ Odd indices เหมือนกัน

→ ใช้ Signature: sorted(even_chars) + sorted(odd_chars) เป็น Key จัดกลุ่ม

ตัวอย่างโค้ด

class Solution:
    def numSpecialEquivGroups(self, A):
        codes = set()
        for word in A:
            # Even indices: word[::2], Odd indices: word[1::2]
            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"]))

ผลลัพธ์

3

Complexity: O(N × K log K) โดย N = จำนวนสตริง, K = ความยาวสตริง (จากการ Sort)