一、题目描述

小F得到了一个特殊的字符串，这个字符串只包含字符A、S、D、F，其长度总是4的倍数。他的任务是通过尽可能少的替换，使得A、S、D、F这四个字符在字符串中出现的频次相等。求出实现这一条件的最小子串长度。

二、思路分析

1. 统计字符频次：

   • 首先需要统计整个字符串中每个字符的初始频次，以便后续分析与目标频次的差距。

2. 判断是否已平衡：

   • 如果四个字符的初始频次已经相等，那么无需进行任何替换，直接返回 0。

3. 尝试不同子串长度：

   • 从长度为 1 的子串开始，逐步增加子串长度，对每个长度的子串进行检查。
   • 对于每个子串长度，遍历字符串中所有该长度的子串起始位置。
   • 计算替换当前子串后的字符频次变化，判断是否能通过在剩余字符串中添加该长度的字符达到平衡

三、解题思路

1. 统计频次：

   • 使用 HashMap 来存储每个字符的频次，初始化四个字符的频次为 0，然后遍历字符串，每遇到一个字符就将其对应频次加 1。

2. 判断平衡：

   • 遍历 freq 中存储的字符频次值，如果有任何一个字符的频次不等于目标频次（字符串长度除以 4），则标记字符串未平衡，否则直接返回 0。

3. 尝试子串：

   • 外层循环从长度 1 到字符串长度，内层循环遍历每个起始位置，得到子串。
   • 对于每个子串，创建一个临时的 HashMap 副本 temp，在副本中减去子串中字符的频次，得到替换子串后的频次情况。
   • 计算 temp 中频次的最大值 maxCount 和最小值 minCount，如果 maxCount - minCount <= length，说明子串内的频次差异在可接受范围内，进一步检查是否能通过分配 length 个字符来达到平衡。
   • 计算需要添加的字符数量 needed，如果 needed <= length，则找到了满足条件的最小子串长度，返回 length。如果遍历完所有子串都未找到，则返回字符串长度 n。

四、代码

public static int solution(String input) {
        int n = input.length();
        int target = n / 4; // 目标频次
        // 统计频次
        Map<Character, Integer> freq = new HashMap<>();
        freq.put('A', 0);
        freq.put('S', 0);
        freq.put('D', 0);
        freq.put('F', 0);
        for (int i = 0; i < n; i++) {
            char c = input.charAt(i);
            freq.put(c, freq.get(c) + 1);
        }
        // 已经平衡
        boolean allEqual = true;
        for (int f : freq.values()) {
            if (f!= target) {
                allEqual = false;
                break;
            }
        }
        if (allEqual) {
            return 0;
        }
        // 尝试每个可能的长度
        for (int length = 1; length <= n; length++) {
            // 检查每个起始位置
            for (int start = 0; start <= n - length; start++) {
                // 计算替换该子串后的频次
                Map<Character, Integer> temp = new HashMap<>(freq);
                for (int i = start; i < start + length; i++) {
                    temp.put(input.charAt(i), temp.get(input.charAt(i)) - 1);
                }
                // 检查是否可以通过添加length个字符达到平衡
                int maxCount = Integer.MIN_VALUE;
                int minCount = Integer.MAX_VALUE;
                for (int count : temp.values()) {
                    maxCount = Math.max(maxCount, count);
                    minCount = Math.min(minCount, count);
                }
                if (maxCount - minCount <= length) {
                    // 检查是否可以分配length个字符来达到平衡
                    int needed = 0;
                    for (int count : temp.values()) {
                        needed += Math.max(0, target - count);
                    }
                    if (needed <= length) {
                        return length;
                    }
                }
            }
        }
        return n;
    }

五、复杂度分析

1. 时间复杂度：

   • 统计字符频次的时间复杂度为 O(n)，其中 n 是字符串长度，因为需要遍历一次字符串。
   • 尝试不同子串长度的部分，外层循环从 1 到 n，内层循环对于每个长度最多遍历 n 次，每次计算子串替换后的频次情况以及检查是否平衡都需要遍历 HashMap，时间复杂度约为 O(1)（因为 HashMap 操作通常接近常数时间），所以这部分总的时间复杂度约为 O(n^2)。
   • 综合起来，整个算法的时间复杂度约为 O(n^2)。

2. 空间复杂度：

   • 需要创建 HashMap 来存储字符频次，最多存储 4 个字符的信息，所以空间复杂度为 O(1)。另外，在尝试子串时创建了临时 HashMap 副本，但由于其大小也固定为 4，所以不会增加整体空间复杂度的量级。

六、优化

1. 双指针滑动窗口优化：

   • 可以使用双指针的滑动窗口思想来优化。维护一个窗口，初始时窗口为空。
   • 移动右指针扩大窗口，同时记录窗口内字符的频次变化，计算窗口内字符频次的最大值 maxCount 和最小值 minCount 以及窗口大小 windowSize。
   • 当 maxCount - minCount <= windowSize 时，说明窗口内的频次差异在可接受范围内，进一步检查是否能通过分配 windowSize 个字符来达到平衡，计算需要添加的字符数量 needed，如果 needed <= windowSize，则找到了满足条件的最小子串长度，返回 windowSize。
   • 如果不满足平衡条件，则移动左指针缩小窗口，继续寻找。这样可以避免对每个子串长度和起始位置的双重循环，减少不必要的计算，将时间复杂度优化到 O(n)。