Every day a Leetcode

题目来源：3138. 同位字符串连接的最小长度

解法1：枚举同位子串的长度

从小到大枚举字符串 t 的长度 len。

因为字符串 s 由字符串 t 和它的同位字符串连接而成，所以 n % len = 0。

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

我的做法是用一个集合 set 保存这些排序后的子串，如果 set.size() > 1，说明不符合要求，直接退出这一次循环。当发现在一次循环中最后 set.size() == 1，说明找到了符合要求的字符串 t，此时的 len 就是同位字符串连接的最小长度。

如果这些因子都不满足要求，答案一定是 n。

代码：

class Solution
{
public:int minAnagramLength(string s){int n = s.length();for (int len = 1; len < n; len++){if (n % len == 0){set<string> set;for (int i = 0; i < n; i += len){string temp = s.substr(i, len);sort(temp.begin(), temp.end());set.insert(temp);if (set.size() > 1)break;}if (set.size() == 1)return len;}}return n;}
};

结果：

复杂度分析：

时间复杂度：O(A*n)，其中 n 是字符串 s 的长度，A 是 n 的因子个数（也就是可枚举的 len 的个数）。

空间复杂度：O(n)，其中 n 是字符串 s 的长度。