shelterofly

目标

给你一个由小写英文字母组成的字符串 s。

如果一个 子串 中所有 不同 字符出现的次数都 相同 ，则称该子串为 平衡 子串。

请返回 s 的 最长平衡子串 的 长度 。

子串 是字符串中连续的、非空 的字符序列。

示例 1：

输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。

示例 2：

输入： s = "zzabccy"
输出： 4
解释：
最长的平衡子串是 "zabc"，因为不同字符 'z'、'a'、'b' 和 'c' 都恰好出现了 1 次。

示例 3：

输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。

说明：

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

思路

定义平衡子串是字符出现次数相同的字符串，给定一个由小写英文字母组成的字符串，返回最长的平衡子串长度。

与 3719.最长平衡子数组I 类似，本题需要保证子串中字母出现的次数都相等，可以统计子串内字母的出现次数并判断是否完全相同。

在遍历的过程中，如何判断出现的字符是否都达到 k 个？字母种类数 * k 应当等于子串长度。

代码

/**
 * @date 2026-02-12 9:19
 */
public class LongestBalanced3713 {

    public int longestBalanced(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            Map<Character, Integer> cnt = new HashMap<>();
            here:
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                cnt.merge(c, 1, Integer::sum);
                int t = cnt.get(c);
                for (Integer value : cnt.values()) {
                    if (value != t) {
                        continue here;
                    }
                }
                res = Math.max(res, j - i + 1);
            }
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums。

如果子数组中 不同偶数 的数量等于 不同奇数 的数量，则称该 子数组 是 平衡的 。

返回 最长 平衡子数组的长度。

子数组 是数组中连续且 非空 的一段元素序列。

示例 1:

输入: nums = [2,5,4,3]
输出: 4
解释:
最长平衡子数组是 [2, 5, 4, 3]。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。

示例 2:

输入: nums = [3,2,2,5,4]
输出: 5
解释:
最长平衡子数组是 [3, 2, 2, 5, 4] 。
它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]。因此，答案是 5。

示例 3:

输入: nums = [1,2,3,2]
输出: 3
解释:
最长平衡子数组是 [2, 3, 2]。
它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]。因此，答案是 3。

说明:

• 1 <= nums.length <= 1500
• 1 <= nums[i] <= 10^5

思路

定义平衡子数组是 不同奇数元素个数 与 不同偶数元素个数 相等的子数组，求数组 nums 的平衡子数组的最大长度。

暴力解法是枚举所有可能的子数组，判断是否是平衡子数组，即子数组中不相同奇数个数与不相同偶数个数是否相等。

无需针对每一个子数组都重新计数，考虑使用两个哈希表分别记录奇数元素与偶数元素的出现次数，判断哈希表中的 key 的个数是否相等即可。注意针对每一个起点，需要重新初始化哈希表。

代码

/**
 * @date 2026-02-10 9:16
 */
public class LongestBalanced3719 {

    public int longestBalanced(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer>[] map = new HashMap[2];
            Arrays.setAll(map, x -> new HashMap<>());
            int l = nums[i] % 2;
            map[l].merge(nums[i], 1, Integer::sum);
            for (int j = i + 1; j < n; j++) {
                int r = nums[j] % 2;
                map[r].merge(nums[j], 1, Integer::sum);
                if (map[l].size() == map[l ^ 1].size()) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

示例 1：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 'a' 要么是 'b'​ 。​

思路

有一个仅包含 a, b 两个字符的字符串 s，如果 a 的左边没有 b，b 的右边没有 a 则认为 s 是平衡的。求使得 s 平衡需要删除的最少次数。

可以枚举分割线，分割线左侧的 b 都要删除，右侧的 a 也要删除，取最小值即可。可以使用前后缀分解来解决。

也可也使用动态规划，定义 dp[i] 表示前 i 个字符平衡需要删除的最小次数。

• 当 i 是 b 时，dp[i] = dp[i - 1]
• 当 i 时 a 时，dp[i] = min(dp[i - 1] + 1, cntB)，其中 cntB 表示 i 前面的 b 的个数

代码

/**
 * @date 2026-02-09 11:31
 */
public class MinimumDeletions1653 {

    public int minimumDeletions(String s) {
        int n = s.length();
        int[] prefixB = new int[n + 1];
        char[] chars = s.toCharArray();
        for (int i = 0; i < n; i++) {
            int c = chars[i] - 'a';
            prefixB[i + 1] = prefixB[i] + c;
        }
        int deletedA = 0;
        int res = Integer.MAX_VALUE;
        for (int i = n - 1; i > 0; i--) {
            int c = chars[i] - 'a';
            if (c == 0) {
                res = Math.min(res, prefixB[i] + deletedA);
                deletedA++;
            }
        }
        res = Math.min(res, deletedA);
        return res;
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k。

如果一个数组的 最大 元素的值 至多 是其 最小 元素的 k 倍，则该数组被称为是 平衡 的。

你可以从 nums 中移除 任意 数量的元素，但不能使其变为 空 数组。

返回为了使剩余数组平衡，需要移除的元素的 最小 数量。

注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。

示例 1:

输入：nums = [2,1,5], k = 2
输出：1
解释：
移除 nums[2] = 5 得到 nums = [2, 1]。
现在 max = 2, min = 1，且 max <= min * k，因为 2 <= 1 * 2。因此，答案是 1。

示例 2:

输入：nums = [1,6,2,9], k = 3
输出：2
解释：
移除 nums[0] = 1 和 nums[3] = 9 得到 nums = [6, 2]。
现在 max = 6, min = 2，且 max <= min * k，因为 6 <= 2 * 3。因此，答案是 2。

示例 3:

输入：nums = [4,6], k = 2
输出：0
解释：
由于 nums 已经平衡，因为 6 <= 4 * 2，所以不需要移除任何元素。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^5

思路

定义平衡数组是 元素最大值 <= k * 元素最小值 的数组。有一个数组 nums，每次操作可以移除一个元素，求使得数组变成平衡数组的最少操作次数。

直接二分查找大于 k * nums[i] 的最小下标 index，删掉的元素是前面 i 个元素（下标 i 其实是第 i + 1 个元素，前面有 i 个），加上 n - 1 - index + 1 个大于 k * nums[i] 的元素。

可以使用滑动窗口，删掉的元素就是总长度减去窗口内的元素，针对每一个 left 将其扩展到最右端，然后移出 left 继续判断。

代码

/**
 * @date 2026-02-06 8:54
 */
public class MinRemoval3634 {

    public int minRemoval(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = n - 1;
        int r = 0;
        for (int l = 0; l < n; l++) {
            while (r < n && (long) nums[l] * k >= nums[r]) {
                r++;
            }
            res = Math.min(res, n - (r - l));
        }
        return res;
    }

}

性能