给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s。
如果一个 子串 中所有 不同 字符出现的次数都 相同，则称该子串为 平衡 子串。
请返回 s 的 最长平衡子串 的 长度 。
子串 是字符串中连续的、非空 的字符序列。
示例 1：
输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。示例 2：
输入： s = "aabcc"
输出： 3
解释：
最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 1 次。示例 3：
输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。说明：
定义平衡子串是字符出现次数相同的字符串，给定一个由 a b c 三种字符组成的字符串，返回最长的平衡子串长度。
// todo
给你一个由小写英文字母组成的字符串 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"。说明：
定义平衡子串是字符出现次数相同的字符串，给定一个由小写英文字母组成的字符串，返回最长的平衡子串长度。
与 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。说明:
提示:
// todo
给你一个整数数组 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。说明:
定义平衡子数组是 不同奇数元素个数 与 不同偶数元素个数 相等的子数组，求数组 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;
}
}
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
示例 1：
输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。示例 2：
输入: root = [2,1,3]
输出: [2,1,3]说明：
将给定的二叉搜索树变平衡。
中序遍历二叉搜索树，结果列表有序，从中间重新构建 BST。
/**
* @date 2026-02-09 8:56
*/
public class BalanceBST1382 {
public TreeNode balanceBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
dfs(list, root);
int l = 0, r = list.size() - 1;
return buildTree(list, l, r);
}
public void dfs(List<Integer> nums, TreeNode node) {
if (node == null) {
return;
}
dfs(nums, node.left);
nums.add(node.val);
dfs(nums, node.right);
}
public TreeNode buildTree(List<Integer> nums, int l, int r) {
if (l == r) {
return new TreeNode(nums.get(l));
} else if (l > r) {
return null;
}
int m = l + (r - l) / 2;
return new TreeNode(nums.get(m), buildTree(nums, l, m - 1), buildTree(nums, m + 1, r));
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
给定一个二叉树，判断它是否是 平衡二叉树 。平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false示例 3：
输入：root = []
输出：true说明：
判断给定二叉树是否是平衡二叉树。
dfs 返回子树高度，判断高度差是否超过 1。
/**
* @date 2026-02-09 11:35
*/
public class IsBalanced110 {
boolean res = true;
public boolean isBalanced(TreeNode root) {
dfs(root);
return res;
}
public int dfs(TreeNode node) {
if (node == null) {
return 0;
}
int lh = dfs(node.left);
int rh = dfs(node.right);
if (Math.abs(lh - rh) > 1) {
res = false;
}
return Math.max(lh, rh) + 1;
}
}
给你一个字符串 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
解释：唯一的最优解是删除最前面两个字符。说明：
有一个仅包含 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，所以不需要移除任何元素。说明：
定义平衡数组是 元素最大值 <= 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;
}
}
给你一个整数数组 nums，它表示一个循环数组。请你遵循以下规则创建一个大小 相同 的新数组 result ：
对于每个下标 i（其中 0 <= i < nums.length），独立执行以下操作：
返回新数组 result。
注意：由于 nums 是循环数组，向右移动超过最后一个元素时将回到开头，向左移动超过第一个元素时将回到末尾。
示例 1：
输入： nums = [3,-2,1,1]
输出： [1,1,1,3]
解释：
对于 nums[0] 等于 3，向右移动 3 步到 nums[3]，因此 result[0] 为 1。
对于 nums[1] 等于 -2，向左移动 2 步到 nums[3]，因此 result[1] 为 1。
对于 nums[2] 等于 1，向右移动 1 步到 nums[3]，因此 result[2] 为 1。
对于 nums[3] 等于 1，向右移动 1 步到 nums[0]，因此 result[3] 为 3。示例 2：
输入： nums = [-1,4,-1]
输出： [-1,-1,4]
解释：
对于 nums[0] 等于 -1，向左移动 1 步到 nums[2]，因此 result[0] 为 -1。
对于 nums[1] 等于 4，向右移动 4 步到 nums[2]，因此 result[1] 为 -1。
对于 nums[2] 等于 -1，向左移动 1 步到 nums[1]，因此 result[2] 为 4。说明：
将循环数组 nums 根据规则转换成一个新数组，新数组下标 i 的值是 nums[offset]，当 nums[i] > 0 时，offset 取 i 右边 nums[i] 个位置上的值，当 nums[i] < 0 时，取 i 左边 nums[i] 个位置上的值，如果为 0，取 nums[i]。
/**
* @date 2026-02-05 8:43
*/
public class ConstructTransformedArray3379 {
public int[] constructTransformedArray_v1(int[] nums) {
int n = nums.length;
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nums[((i + nums[i]) % n + n) % n];
}
return res;
}
}
给你一个长度为 n 的整数数组 nums。
三段式子数组 是一个连续子数组 nums[l...r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：
请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其 最大 和。
示例 1：
输入：nums = [0,-2,-1,-3,0,2,-1]
输出：-4
解释：
选择 l = 1, p = 2, q = 3, r = 5：
nums[l...p] = nums[1...2] = [-2, -1] 严格递增 (-2 < -1)。
nums[p...q] = nums[2...3] = [-1, -3] 严格递减 (-1 > -3)。
nums[q...r] = nums[3...5] = [-3, 0, 2] 严格递增 (-3 < 0 < 2)。
和 = (-2) + (-1) + (-3) + 0 + 2 = -4。示例 2:
输入: nums = [1,4,2,7]
输出: 14
解释:
选择 l = 0, p = 1, q = 2, r = 3：
nums[l...p] = nums[0...1] = [1, 4] 严格递增 (1 < 4)。
nums[p...q] = nums[1...2] = [4, 2] 严格递减 (4 > 2)。
nums[q...r] = nums[2...3] = [2, 7] 严格递增 (2 < 7)。
和 = 1 + 4 + 2 + 7 = 14。说明:
3637.三段式数组I 判断是否是三段式数组，本题则是计算数组的三段式子数组的最大和。
定义 dp[k][i] 表示第 k 段以 i 结尾的前 k 段子数组的最大和，其中 k ∈ [0.2]。由于每一段至少有两个元素，如果 i - 1 是该段的起始，根据前面的定义，应该属于 k - 1 段。因此有 dp[k][i] = Math.max(dp[k - 1][i - 1], dp[k][i - 1]) + nums[i]，当 k = 0 时，将 dp[k - 1][i - 1] 替换为 nums[i - 1] 即可。如果处于严格递增段，可以是第一段或第三段，如果处于严格递减段，则只能是第二段。
/**
* @date 2026-02-04 8:57
*/
public class MaxSumTrionic3640 {
public long maxSumTrionic(int[] nums) {
int n = nums.length;
long[][] dp = new long[3][n];
for (int k = 0; k < 3; k++) {
Arrays.fill(dp[k], Long.MIN_VALUE / 2);
}
long res = Long.MIN_VALUE / 2;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
dp[0][i] = Math.max(nums[i - 1], dp[0][i - 1]) + nums[i];
dp[2][i] = Math.max(dp[1][i - 1], dp[2][i - 1]) + nums[i];
} else if (nums[i] < nums[i - 1]) {
dp[1][i] = Math.max(dp[0][i - 1], dp[1][i - 1]) + nums[i];
}
res = Math.max(res, dp[2][i]);
}
return res;
}
}
