class Solution {
public:
int minAnagramLength(string s) {
}
};
3138. 同位字符串连接的最小长度
给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。
请你返回字符串 t 的 最小 可能长度。
同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。
示例 1：
输入：s = "abba"
输出：2
解释：
一个可能的字符串 t 为 "ba" 。
示例 2：
输入：s = "cdef"
输出：4
解释：
一个可能的字符串 t 为 "cdef" ，注意 t 可能等于 s 。
提示：
1 <= s.length <= 105s 只包含小写英文字母。原站题解
golang 解法, 执行用时: 17 ms, 内存消耗: 5.3 MB, 提交时间: 2024-05-06 10:17:08
func minAnagramLength(s string) int {
n := len(s)
next:
for k := 1; k <= n/2; k++ {
if n%k > 0 {
continue
}
cnt0 := [26]int{}
for _, b := range s[:k] {
cnt0[b-'a']++
}
for i := k * 2; i <= len(s); i += k {
cnt := [26]int{}
for _, b := range s[i-k : i] {
cnt[b-'a']++
}
if cnt != cnt0 {
continue next
}
}
return k
}
return n
}
java 解法, 执行用时: 24 ms, 内存消耗: 46 MB, 提交时间: 2024-05-06 10:16:31
class Solution {
public int minAnagramLength(String S) {
char[] s = S.toCharArray();
int n = s.length;
next:
for (int k = 1; k <= n / 2; k++) {
if (n % k > 0) {
continue;
}
int[] cnt0 = new int[26];
for (int j = 0; j < k; j++) {
cnt0[s[j] - 'a']++;
}
for (int i = k * 2; i <= n; i += k) {
int[] cnt = new int[26];
for (int j = i - k; j < i; j++) {
cnt[s[j] - 'a']++;
}
if (!Arrays.equals(cnt, cnt0)) {
continue next;
}
}
return k;
}
return n;
}
}
cpp 解法, 执行用时: 60 ms, 内存消耗: 12.1 MB, 提交时间: 2024-05-06 10:16:19
class Solution {
public:
int minAnagramLength(string s) {
int n = s.length();
for (int k = 1; k <= n / 2; k++) {
if (n % k) {
continue;
}
array<int, 26> cnt0{};
for (int j = 0; j < k; j++) {
cnt0[s[j] - 'a']++;
}
for (int i = k * 2; i <= n; i += k) {
array<int, 26> cnt{};
for (int j = i - k; j < i; j++) {
cnt[s[j] - 'a']++;
}
if (cnt != cnt0) {
goto next;
}
}
return k;
next:;
}
return n;
}
};
python3 解法, 执行用时: 1329 ms, 内存消耗: 16.9 MB, 提交时间: 2024-05-06 10:15:57
# 枚举n的因子，最多128个
'''
s 的长度为 n，t的长度为k，k为n的因子。
10^5以内的因子个数最多128，所以暴力枚举n的因子作为k。
然后比较所有首字母下标为 0,k,2k,3k,...,n-k 的长为 k 的子串，所包含的字母及其个数是否一样。
'''
class Solution:
def minAnagramLength(self, s: str) -> int:
n = len(s)
for k in range(1, n // 2 + 1):
if n % k:
continue
cnt0 = Counter(s[:k])
for i in range(k * 2, n + 1, k):
if Counter(s[i - k: i]) != cnt0:
break
else:
return k
return n
def minAnagramLength2(self, s: str) -> int:
n = len(s)
for k in range(1, n // 2 + 1):
if n % k:
continue
cnt0 = Counter(s[:k])
if all(Counter(s[i - k: i]) == cnt0 for i in range(k * 2, n + 1, k)):
return k
return n
def minAnagramLength3(self, s: str) -> int:
n = len(s)
for k in range(1, n // 2 + 1):
if n % k:
continue
t = sorted(s[:k])
if all(sorted(s[i - k: i]) == t for i in range(k * 2, n + 1, k)):
return k
return n