- Leetcode 3138. Minimum Length of Anagram Concatenation
- 1. 解题思路
- 2. 代码实现
- 题目链接:3138. Minimum Length of Anagram Concatenation
1. 解题思路
这一题的话我们首先统计出来所有的字母出现的频率。
然后,我们只需要从头开始重新计数一下,当出现的第一个位置满足所有的字母出现的频次均为所有频次的 1 / k 1/k 1/k时,即可满足条件,我们返回当前的subarray的长度即可。
2. 代码实现
给出python代码实现如下:
class Solution:
def minAnagramLength(self, s: str) -> int:
cnt = Counter(s)
cnt = [cnt[ch] for ch in string.ascii_lowercase]
def is_divisible(cnt, _cnt):
if any(x != 0 and y == 0 for x, y in zip(cnt, _cnt)):
return False
k = -1
for i in range(26):
if cnt[i] == 0:
continue
if cnt[i] % _cnt[i] != 0:
return False
if k == -1:
k = cnt[i] // _cnt[i]
else:
if cnt[i] // _cnt[i] != k:
return False
return True
stat = [0 for _ in range(26)]
for i, ch in enumerate(s):
stat[ord(ch) - ord('a')] += 1
if is_divisible(cnt, stat):
return i+1
return len(s)
提交代码评测得到:耗时731ms,占用内存17.5MB。