题目描述
给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。
请你返回字符串 t 的 最小 可能长度。
同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。
示例 1：
输入：s = "abba"
输出：2
解释：
一个可能的字符串 t 为 "ba" 。
示例 2：
输入：s = "cdef"
输出：4
解释：
一个可能的字符串 t 为 "cdef" ，注意 t 可能等于 s 。
提示：
1 <= s.length <= 105s 只包含小写英文字母。
解法
方法一：枚举
根据题目描述，字符串 $\textit{t}$ 的长度一定是 $\textit{s}$ 的长度的因子，我们可以从小到大枚举字符串 $\textit{t}$ 的长度 $k$，然后检查是否满足题目要求，如果满足则返回。因此，问题转化为如何检查字符串 $\textit{t}$ 的长度 $k$ 是否满足题目要求。
我们首先统计字符串 $\textit{s}$ 中每个字符出现的次数，记录在数组或哈希表 $\textit{cnt}$ 中。
然后，我们定义一个函数 $\textit{check}(k)$，用来检查字符串 $\textit{t}$ 的长度 $k$ 是否满足题目要求。我们可以遍历字符串 $\textit{s}$，每次取长度为 $k$ 的子串，然后统计每个字符出现的次数，如果每个字符出现的次数乘以 $\frac{n}{k}$ 不等于 $\textit{cnt}$ 中的值，则返回 $\textit{false}$。遍历结束，如果都满足，则返回 $\textit{true}$。
时间复杂度 $O(n \times A)$，其中 $n$ 是字符串 $\textit{s}$ 的长度，而 $A$ 是 $n$ 的因子个数。空间复杂度 $O(|\Sigma|)$，其中 $\Sigma$ 是字符集，本题中为小写字母集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def minAnagramLength(self, s: str) -> int:
def check(k: int) -> bool:
for i in range(0, n, k):
cnt1 = Counter(s[i : i + k])
for c, v in cnt.items():
if cnt1[c] * (n // k) != v:
return False
return True
cnt = Counter(s)
n = len(s)
for i in range(1, n + 1):
if n % i == 0 and check(i):
return i
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
private int n;
private char[] s;
private int[] cnt = new int[26];
public int minAnagramLength(String s) {
n = s.length();
this.s = s.toCharArray();
for (int i = 0; i < n; ++i) {
++cnt[this.s[i] - 'a'];
}
for (int i = 1;; ++i) {
if (n % i == 0 && check(i)) {
return i;
}
}
}
private boolean check(int k) {
for (int i = 0; i < n; i += k) {
int[] cnt1 = new int[26];
for (int j = i; j < i + k; ++j) {
++cnt1[s[j] - 'a'];
}
for (int j = 0; j < 26; ++j) {
if (cnt1[j] * (n / k) != cnt[j]) {
return false;
}
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public:
int minAnagramLength(string s) {
int n = s.size();
int cnt[26]{};
for (char c : s) {
cnt[c - 'a']++;
}
auto check = [&](int k) {
for (int i = 0; i < n; i += k) {
int cnt1[26]{};
for (int j = i; j < i + k; ++j) {
cnt1[s[j] - 'a']++;
}
for (int j = 0; j < 26; ++j) {
if (cnt1[j] * (n / k) != cnt[j]) {
return false;
}
}
}
return true;
};
for (int i = 1;; ++i) {
if (n % i == 0 && check(i)) {
return i;
}
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | func minAnagramLength(s string) int {
n := len(s)
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
check := func(k int) bool {
for i := 0; i < n; i += k {
cnt1 := [26]int{}
for j := i; j < i+k; j++ {
cnt1[s[j]-'a']++
}
for j, v := range cnt {
if cnt1[j]*(n/k) != v {
return false
}
}
}
return true
}
for i := 1; ; i++ {
if n%i == 0 && check(i) {
return i
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | function minAnagramLength(s: string): number {
const n = s.length;
const cnt: Record<string, number> = {};
for (let i = 0; i < n; i++) {
cnt[s[i]] = (cnt[s[i]] || 0) + 1;
}
const check = (k: number): boolean => {
for (let i = 0; i < n; i += k) {
const cnt1: Record<string, number> = {};
for (let j = i; j < i + k; j++) {
cnt1[s[j]] = (cnt1[s[j]] || 0) + 1;
}
for (const [c, v] of Object.entries(cnt)) {
if (cnt1[c] * ((n / k) | 0) !== v) {
return false;
}
}
}
return true;
};
for (let i = 1; ; ++i) {
if (n % i === 0 && check(i)) {
return i;
}
}
}
|