每个字符恰好出现两次的最长子字符串 #

给你一个字符串 s ，请找出满足每个字符恰好出现两次的最长子字符串，并返回该子字符串的最大长度。

示例 1：

输入： s = “bcbbbcca”

输出： 4

解释：以下子字符串长度为 4，并且每个字符出现两次：“bbcc”。

示例 2：

输入： s = “aaaa”

输出： 2

解释：以下子字符串长度为 2，并且每个字符最多出现两次：“aa”。提示： 2 <= s.length <= 100 s 仅由小写英文字母组成。

解答 #

下面给出两种解法，均能求解“每个字符恰好出现两次的最长子字符串”的最大长度。注意：由于要求子串中每个出现的字符次数均为 2，所以这样的子串长度必定为偶数，且若子串中有 kkk 个不同的字符，则子串长度为 2k2k2k。

解法一：暴力枚举（双重循环维护滑动窗口） #

思路分析 #

我们可以枚举字符串中所有可能的子串，对于每个子串：

先判断长度是否为偶数，不是偶数则肯定不可能满足“每个字符出现两次”；
利用一个长度为 26 的频率数组统计子串中每个字符出现的次数；
检查频率数组中：对于每个出现的字符，其次数是否恰好为 2；
如果满足条件，则更新答案。

由于字符串长度 nnn 最多 100，因此使用两层循环枚举子串（时间复杂度 $O(n^2)$ ），再加上检查频率数组的 26 个字母，整体复杂度为 $O(26\cdot n^2)$ ，对于本题规模是足够的。

JAVA代码 #

javaCopypublic class LongestSubstringBruteForce {
    public static int longestSubstring(String s) {
        int n = s.length();
        int maxLen = 0;
        
        // 枚举所有子串的起点 i
        for (int i = 0; i < n; i++) {
            // 用数组统计字符频率
            int[] freq = new int[26];
            // 枚举子串终点 j
            for (int j = i; j < n; j++) {
                // 更新 s.charAt(j) 的频率
                freq[s.charAt(j) - 'a']++;
                
                // 子串长度必须为偶数才能可能满足条件
                if ((j - i + 1) % 2 != 0) {
                    continue;
                }
                
                // 检查子串中出现的每个字符是否均出现两次
                boolean valid = true;
                for (int k = 0; k < 26; k++) {
                    // 如果字符出现了但次数不为2，则不满足条件
                    if (freq[k] != 0 && freq[k] != 2) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
    
    // 测试代码
    public static void main(String[] args) {
        String s1 = "bcbbbcca";
        String s2 = "aaaa";
        System.out.println("输入: " + s1 + "，输出: " + longestSubstring(s1)); // 期望输出 4
        System.out.println("输入: " + s2 + "，输出: " + longestSubstring(s2)); // 期望输出 2
    }
}

复杂度分析 #

时间复杂度：外层循环 O(n)，内层循环 O(n)；每次检查 26 个字符，故整体复杂度为 $O(26\cdot n^2)$ 。
空间复杂度：使用了大小为 26 的数组，所以为 O(1)。

解法二：滑动窗口（固定窗口长度枚举） #

思路分析 #

由于要求子串中每个出现的字符出现次数均为 2，所以若子串中有 k个不同字符，则子串长度一定为 2k。因此我们可以按可能的不同字符个数 k 枚举（注意 k 最大不超过 s.length()/2），对于每个 k：

设窗口大小 L=2k；
利用滑动窗口在字符串上移动，维护窗口中每个字符的频率；
对于每个窗口，检查：如果窗口中出现的字符个数恰好为 kkk 并且每个字符的频率均为 2，则该窗口有效；
为了找到最长的子串，我们可以从 kkk 较大的情况开始枚举（从 s.length()/2递减到 1），一旦找到了一个有效窗口，即可直接返回结果。

这样做的总体复杂度为：对于每个 k（最多 50 种可能），滑动窗口的移动时间 O(n)，每次检查 26 个字母，故总复杂度为 $O(26\cdot n \cdot (n/2))$ ，对于 $n\le 100$ 足够高效。

JAVA代码 #

javaCopypublic class LongestSubstringSlidingWindow {
    public static int longestSubstring(String s) {
        int n = s.length();
        // 从最大的可能不同字符个数开始枚举
        for (int distinct = n / 2; distinct >= 1; distinct--) {
            int windowSize = distinct * 2;
            if (windowSize > n) {
                continue;
            }
            // 使用频率数组记录窗口内各字符出现次数
            int[] freq = new int[26];
            // 处理第一个窗口 [0, windowSize-1]
            for (int i = 0; i < windowSize; i++) {
                freq[s.charAt(i) - 'a']++;
            }
            if (isValid(freq)) {
                return windowSize;
            }
            // 滑动窗口，i为窗口起点
            for (int i = 1; i + windowSize - 1 < n; i++) {
                // 移除窗口最左边的字符
                freq[s.charAt(i - 1) - 'a']--;
                // 添加新的字符
                freq[s.charAt(i + windowSize - 1) - 'a']++;
                if (isValid(freq)) {
                    return windowSize;
                }
            }
        }
        // 没有找到满足条件的子串返回 0
        return 0;
    }
    
    // 辅助函数：检查窗口内的频率数组是否满足每个出现的字符均恰好出现2次
    private static boolean isValid(int[] freq) {
        for (int count : freq) {
            if (count != 0 && count != 2) {
                return false;
            }
        }
        return true;
    }
    
    // 测试代码
    public static void main(String[] args) {
        String s1 = "bcbbbcca";
        String s2 = "aaaa";
        System.out.println("输入: " + s1 + "，输出: " + longestSubstring(s1)); // 期望输出 4
        System.out.println("输入: " + s2 + "，输出: " + longestSubstring(s2)); // 期望输出 2
    }
}

复杂度分析 #

时间复杂度：外层枚举 distinct的次数最多为 n/2（即 O(n)），每次滑动窗口遍历字符串 O(n)，检查频率数组 O(26)。总体复杂度为 $O(26 \cdot n \cdot n/2) = O(n^2)$ 。
空间复杂度：仅使用了大小为 26 的频率数组，故为O(1)。

总结 #

两种解法均能正确求解该问题：

解法一 利用两层循环直接枚举所有子串（可视作滑动窗口的简单应用），实现简单，时间复杂度 $O(n^2)$ 。
解法二 则利用固定窗口大小的滑动窗口，并从可能的最大长度开始尝试，一旦找到有效窗口即可返回答案，同样总体复杂度为 $O(n^2)$ 。

两种方法都适用于字符串长度较小的情况（本题 $n \le 100$ ）。