力扣12-20每日一题

3138. 同位字符串连接的最小长度

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

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

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

示例 1：

输入：s = “abba”

输出：2

解释：

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

示例 2：

输入：s = “cdef”

输出：4

解释：

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

提示：

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

两种方法：枚举因子 / 枚举次数 + GCD 优化

方法一：枚举长度

设 s 的长度为 n，t 的长度为 k。

由于 s 是由若干长度为 k 的字符串拼接而成，所以 k 一定是 n 的因子。

由于 105 以内的数，因子个数至多为 128（83160 的因子个数），所以我们可以暴力枚举 n 的因子 k。

然后比较所有首字母下标为 0,k,2k,3k,⋯,n−k 的长为 k 的子串，所包含的字母及其个数是否一样（同位字符串）。

注意只需枚举小于 n 的因子，如果这些因子都不满足要求，答案一定是 n（如示例 2）。

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']++;
            }
            bool ok = true;
            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) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return k;
            }
        }
        return n;
    }
};

复杂度分析

  • 时间复杂度：O(A⋅n)，其中 n 为 s 的长度，A 为 n 的因子个数。
  • 空间复杂度：O(∣Σ∣)。其中 ∣Σ∣ 为字符集合的大小，本题字符均为小写字母，所以 ∣Σ∣=26。

方法二：枚举次数 + GCD 优化

假设 s 由 6 个 a 和 4 个 b 组成。

那么 t 中的 a 的个数，必须是 6 的因子，这是 t 能连接得到 s 的必要条件。

比如 t 中有 3 个 a，那么 s 由 times=36=2 个 t 和 t 的同位字符串连接而成。注意这里的 2 也是 6 的因子。

同时 t 中的 b 的个数，必须是 4 的因子。所以 times 也必须是 4 的因子。

所以 times 必须是 6 和 4 的公因子，也就是 g=GCD(6,4)=2 的因子。

从大到小枚举 g 的因子 times=g,g−1,…,2，那么方法一中的 k=times**n。后续逻辑同方法一。

如果枚举到 times=2 也没有找到答案，那么答案是 n。

class Solution {
public:
    int minAnagramLength(string s) {
        int n = s.length();
        int cnt_all[26]{};
        for (char c : s) {
            cnt_all[c-'a']++;
        }
        int g = 0;
        for (int c : cnt_all) {
            g = gcd(g, c);
        }
        for (int times = g; times > 1; times--) {
            if (g % times) {
                continue;
            }
            int k = n / times;
            array<int, 26> cnt0{};
            for (int j = 0; j < k; j++) {
                cnt0[s[j] - 'a']++;
            }
            bool ok = true;
            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) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return k;
            }
        }
        return n;
    }
};

复杂度分析

  • 时间复杂度：O(A⋅n)，其中 n 为 s 的长度，A 为 n 的因子个数。
  • 空间复杂度：O(∣Σ∣)。其中 ∣Σ∣ 为字符集合的大小，本题字符均为小写字母，所以 ∣Σ∣=26。