Medium

题目描述

给你一个字符串 s，已知它是某个字符串 t 的字母异位词的连接。

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

字母异位词是通过重新排列字符串的字母形成的。例如，“aab”、“aba” 和 “baa” 都是 “aab” 的字母异位词。

示例 1：

输入：s = "abba"
输出：2
解释：
一个可能的字符串 t 可以是 "ba"。

示例 2：

输入：s = "cdef"
输出：4
解释：
一个可能的字符串 t 可以是 "cdef"，注意 t 可以等于 s。

示例 3：

输入：s = "abcbcacabbaccba"
输出：3

约束条件：

  • 1 <= s.length <= 10^5
  • s 仅由小写英文字母组成。

提示：

  • 答案应该是 s.length 的因数。
  • 朴素地检查每个候选值。

解题思路

这道题的关键在于理解题意：字符串 s 是由多个字符串 t 的字母异位词连接而成的，我们需要找到 t 的最小可能长度。

解题思路：

  1. 因数枚举：由于 s 是由若干个长度为 len(t) 的字母异位词连接而成，所以 len(t) 必须是 len(s) 的因数。

  2. 验证策略：对于每个可能的长度 k（len(s) 的因数），我们将字符串 s 按长度 k 分割成若干段，检查这些段是否都是同一个字符串的字母异位词。

  3. 字母异位词判断：两个字符串是字母异位词当且仅当它们包含相同的字符且每个字符的出现次数相同。我们可以通过字符计数来验证。

  4. 优化：从小到大枚举因数，找到第一个满足条件的长度就是答案，因为我们要求最小长度。

算法步骤：

  • 遍历 s.length 的所有因数
  • 对于每个因数 k，将字符串按长度 k 分段
  • 统计第一段的字符频次作为基准
  • 检查其他所有段的字符频次是否与基准相同
  • 如果都相同，返回 k；否则继续下一个因数

代码实现

class Solution {
public:
    int minAnagramLength(string s) {
        int n = s.length();
        
        for (int k = 1; k <= n; k++) {
            if (n % k != 0) continue;
            
            // 统计第一段的字符频次
            vector<int> count(26, 0);
            for (int i = 0; i < k; i++) {
                count[s[i] - 'a']++;
            }
            
            bool valid = true;
            // 检查其他段
            for (int start = k; start < n && valid; start += k) {
                vector<int> segmentCount(26, 0);
                for (int i = start; i < start + k; i++) {
                    segmentCount[s[i] - 'a']++;
                }
                if (segmentCount != count) {
                    valid = false;
                }
            }
            
            if (valid) return k;
        }
        
        return n;
    }
};

class Solution:
    def minAnagramLength(self, s: str) -> int:
        n = len(s)
        
        for k in range(1, n + 1):
            if n % k != 0:
                continue
            
            # 统计第一段的字符频次
            from collections import Counter
            base_count = Counter(s[:k])
            
            valid = True
            # 检查其他段
            for start in range(k, n, k):
                segment_count = Counter(s[start:start + k])
                if segment_count != base_count:
                    valid = False
                    break
            
            if valid:
                return k
        
        return n

public class Solution {
    public int MinAnagramLength(string s) {
        int n = s.Length;
        
        for (int k = 1; k <= n; k++) {
            if (n % k != 0) continue;
            
            // 统计第一段的字符频次
            int[] count = new int[26];
            for (int i = 0; i < k; i++) {
                count[s[i] - 'a']++;
            }
            
            bool valid = true;
            // 检查其他段
            for (int start = k; start < n && valid; start += k) {
                int[] segmentCount = new int[26];
                for (int i = start; i < start + k; i++) {
                    segmentCount[s[i] - 'a']++;
                }
                
                for (int i = 0; i < 26; i++) {
                    if (segmentCount[i] != count[i]) {
                        valid = false;
                        break;
                    }
                }
            }
            
            if (valid) return k;
        }
        
        return n;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var minAnagramLength = function(s) {
    const n = s.length;
    
    for (let k = 1; k <= n; k++) {
        if (n % k !== 0) continue;
        
        // 统计第一段的字符频次
        const count = new Array(26).fill(0);
        for (let i = 0; i < k; i++) {
            count[s.charCodeAt(i) - 97]++;
        }
        
        let valid = true;
        // 检查其他段
        for (let start = k; start < n && valid; start += k) {
            const segmentCount = new Array(26).fill(0);
            for (let i = start; i < start + k; i++) {
                segmentCount[s.charCodeAt(i) - 97]++;
            }
            
            for (let i = 0; i < 26; i++) {
                if (segmentCount[i] !== count[i]) {
                    valid = false;
                    break;
                }
            }
        }
        
        if (valid) return k;
    }
    
    return n;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × d(n))，其中 d(n) 是 n 的因数个数。对于每个因数，需要 O(n) 时间验证所有段
空间复杂度O(1)，只使用固定大小的字符计数数组