3138. Minimum Length of Anagram Concatenation

Problem Link

Description

---

You are given a string s, which is known to be a concatenation of anagrams of some string t.

Return the minimum possible length of the string t.

An anagram is formed by rearranging the letters of a string. For example, "aab", "aba", and, "baa" are anagrams of "aab".

 

Example 1:

Input: s = "abba"

Output: 2

Explanation:

One possible string t could be "ba".

Example 2:

Input: s = "cdef"

Output: 4

Explanation:

One possible string t could be "cdef", notice that t can be equal to s.

Example 2:

Input: s = "abcbcacabbaccba"

Output: 3

 

Constraints:

• 1 <= s.length <= 105
• s consist only of lowercase English letters.

Solution

---

Python3

class Solution:
    def minAnagramLength(self, s: str) -> int:
        N = len(s)
 
        def good(k):
            cnt = [0] * 26
 
            for i in range(k):
                cnt[ord(s[i]) - ord('a')] += 1
            
            for i in range(k, N - k + 1, k):
                cnt2 = [0] * 26
                for j in range(i, i + k):
                    cnt2[ord(s[j]) - ord('a')] += 1
                
                for j in range(26):
                    if cnt[j] != cnt2[j]:
                        return False
            
            return True
 
        for i in range(1, N):
            if N % i == 0 and good(i):
                return i
        
        return N