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

题目链接

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

分析

设字符串 $s$ 得长度为 $n$

由题意可得，字符串 $t$ 得长度一定是 $n$ 得因数（不然 $x$ 个 $t$ 无法拼接成 $s$）

那么，枚举 $n$ 得因数进行验证即可

代码实现

class Solution {
public:
    int minAnagramLength(string s) {
        int n = s.size();

        auto check = [&](int x) -> bool
        {
            vector<int> simple(26);
            for(int i = 0; i < x; ++i)
                simple[s[i] - 'a']++;
  
            for(int j = x; j < n; j += x)
            {
                vector<int> t(26);
                for(int k = j; k < j + x; ++k)
                    t[s[k] - 'a']++;
                if(t != simple)
                    return false;
            }
            return true;
        };

        for(int i = 1; i < n; ++i)
            if(!(n % i) && check(i))
                return i;
        return n;
    }
};

复杂度分析

• 时间复杂度：$O(nP)$，其中 $n$ 是 $s$ 的长度，$P$ 是 $n$ 的因数个数
• 空间复杂度：$O(|Σ|)$，其中 $|Σ|=26$ ，为字符集的大小