LeetCode 3138. Minimum Length of Anagram Concatenation

May 5, 2024

周賽 396。又是超級爛的題目描述，不管 LCUS 原文或是 LCCN 的翻譯都很爛，不知道在搞什麼。
描述偷改過了，原本好像是講：

typically using all the original letters exactly once

結果一堆人用 GCD 去做 (包括我)。
而已近 600 個測資都沒有攔截到，某方面來講也是很厲害，明明簡單的 “aabb” 就可以擋下。

中文翻譯也很厲害：

给你一个字符串 s ，它由某个字符串 t 和它的同位字符串连接而成

真是夢回當年國文課，猜第二個它是指誰？

題目

輸入字串 s，且 s 是由 t 的易位構詞依序連接而成。

求字串 t 可能的最小長度。

易位構詞是將一個字串的字元重新排列而成。例如：”aab” 的易位構詞有 “aab”, “aba” 和 “baa”。

解法

其實跟上一題有點相似，只是要找到某個長度為 size 的字串 t，且每個長度為 t 的子字串都是易位構詞。

判斷易位構詞方法很多。
對於 python 來說，最快的方式就是把兩個字串排序、或是丟到字典裡比對。
冷知識：排序複雜度高，但執行起來反而快。

題目要找最小值，因此從 1 開始枚舉 size，若每個大小為 size 的子字串都滿足易位構詞，則回傳 size。

每次枚舉一個長度 size，需要遍歷字串一次，是 O(N)。
只有在 size 能夠整除 s 的情況下才有可能是答案。而 size 最多只會有 sqrt(size) * 2 個因數。

時間複雜度 O(sqrt(N) * N)。
空間複雜度 O(1)。

class Solution:
    def minAnagramLength(self, s: str) -> int:
        N = len(s)
        
        for size in range(1, N):
            if N % size != 0:
                continue
            target = Counter(s[:size])
            for i in range(0, N, size):
                if target != Counter(s[i:i + size]):
                    break
            else:
                return size
            
        return N

mocowcow

題目

解法