当前位置：首页 > article >正文

LeetCode 3138.同位字符串连接的最小长度：计数（一个数最多128个因数）

article 2024/12/26 0:56:57

【LetMeFly】3138.同位字符串连接的最小长度：计数（一个数最多128个因数）

力扣题目链接：https://leetcode.cn/problems/minimum-length-of-anagram-concatenation/

给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。

请你返回字符串 t 的最小可能长度。

同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。

示例 1：

输入：s = "abba"

输出：2

解释：

一个可能的字符串 t 为 "ba" 。

示例 2：

输入：s = "cdef"

输出：4

解释：

一个可能的字符串 t 为 "cdef" ，注意 t 可能等于 s 。

提示：

1 <= s.length <= 10⁵
s 只包含小写英文字母。

解题方法：计数

$1$ 到 $10^5$ 范围内的一个数，最多有多少个因子呢？

from math import sqrt

M, Mi = 0, 0

def getYin(n: int) -> int:
    k = int(sqrt(n))
    ans = 0
    for i in range(1, k):
        if n % i == 0:
            ans += 2
    if k * k == n:
        ans += 1
    return ans

for n in range(1, 100001):
    yinN = getYin(n)
    if yinN > M:
        M, Mi = yinN, n
print(f'{Mi}因子数最多，为{M}个')

83160因子数最多，为128个。

首先从 $1$ 到 $l e n (s)$ 模拟同位字符串的长度 $an s$ ：

如果 $an s$ 不是字符串 $s$ 长度的因数，则 $an s$ 一定不可行。

否则，每 $an s$ 长度统计一次子字符串中每个字母分别出现了多少次。如果全相同，则返回 $an s$ 。

时间复杂度 $O(A\times len(s))$ ，其中 $A$ 为 $1$ 到 $l e n (s)$ 的整数中的最大因子个数。
空间复杂度 $O (C)$ ，其中 $C = 26$ 。

AC代码

C语言

/*
 * @Author: LetMeFly
 * @Date: 2024-12-20 21:06:55
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-12-20 21:14:34
 */
void count(int times[], char s[], int l, int r) {
    for (int i = l; i < r; i++) {
        times[s[i] - 'a']++;
    }
}

int same26(int a[], int b[]) {
    for (int i = 0; i < 26; i++) {
        if (a[i] != b[i]) {
            return 0;
        }
    }
    return 1;
}

int minAnagramLength(char* s) {
    int n = strlen(s);
    for (int ans = 1; ans < n; ans++) {
        if (n % ans) {
            continue;
        }
        int should[26] = {0};
        count(should, s, 0, ans);
        for (int i = ans; i < n; i += ans) {
            int now[26] = {0};
            count(now, s, i, i + ans);
            if (!same26(should, now)) {
                goto loop;
            }
        }
        return ans;
        loop:;
    }
    return n;
}

C++

/*
 * @Author: LetMeFly
 * @Date: 2024-12-20 20:56:59
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-12-20 20:57:22
 */
class Solution {
private:
    vector<int> count(string& s, int l, int r) {
        vector<int> ans(26);
        for (int i = l; i < r; i++) {
            ans[s[i] - 'a']++;
        }
        return ans;
    }
public:
    int minAnagramLength(string& s) {
        for (int ans = 1; ans < s.size(); ans++) {
            if (s.size() % ans) {
                continue;
            }
            vector<int> should = count(s, 0, ans);
            for (int i = ans; i < s.size(); i += ans) {
                vector<int> now = count(s, i, i + ans);
                if (should != now) {
                    goto loop;
                }
            }
            return ans;
            loop:;
        }
        return s.size();
    }
};

Python

'''
Author: LetMeFly
Date: 2024-12-20 20:53:20
LastEditors: LetMeFly.xyz
LastEditTime: 2024-12-20 20:56:17
'''
from collections import Counter

class Solution:
    def minAnagramLength(self, s: str) -> int:
        for ans in range(1, len(s)):
            if len(s) % ans:
                continue
            should = Counter(s[:ans])
            ok = True
            for i in range(ans, len(s), ans):
                if should != Counter(s[i:i + ans]):
                    ok = False
                    break
            if ok:
                return ans
        return len(s)

Java

/*
 * @Author: LetMeFly
 * @Date: 2024-12-20 20:58:29
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-12-20 21:05:54
 */
import java.util.Arrays;

class Solution {
    private int[] count(char[] s, int l, int r) {
        int[] ans = new int[26];
        for (int i = l; i < r; i++) {
            ans[s[i] - 'a']++;
        }
        return ans;
    }
    public int minAnagramLength(String S) {
        char[] s = S.toCharArray();
        loop:
        for (int ans = 1; ans < s.length; ans++) {
            if (s.length % ans != 0) {
                continue;
            }
            int[] should = count(s, 0, ans);
            for (int i = ans; i < s.length; i += ans) {
                int[] now = count(s, i, i + ans);
                if (!Arrays.equals(should, now)) {
                    continue loop;
                }
            }
            return ans;
        }
        return s.length;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2024-12-20 21:16:18
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-12-20 21:20:42
 */
package main

func count(s string, l, r int) []int {
    ans := make([]int, 26)
    for i := l; i < r; i++ {
        ans[s[i] - 'a']++
    }
    return ans
}

func same26(a, b []int) bool {
    for i := range a {
        if a[i] != b[i] {
            return false;
        }
    }
    return true;
}

func minAnagramLength(s string) int {
    for ans := 1; ans < len(s); ans++ {
        if len(s) % ans != 0 {
            continue
        }
        should := count(s, 0, ans)
        ok := true
        for i := ans; i < len(s); i += ans {
            if !same26(should, count(s, i, i + ans)) {
                ok = false
                break
            }
        }
        if ok {
            return ans
        }
    }
    return len(s)
}