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
.
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