标签： 枚举

696.计数二进制子串

目标

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

示例 1：

输入：s = "00110011"
输出：6
解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：

输入：s = "10101"
输出：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

说明：

  • 1 <= s.length <= 10^5
  • s[i] 为 '0' 或 '1'

思路

统计二进制字符串 s 中满足条件的子串个数。子串需满足 0 与 1 的个数相等，且子串中所有 0 都是相邻且连续的（由于数量相同，子串中所有的 1 也是相邻且连续的），即 0 与 1 都是成组连续的。

00011 满足条件的子串个数为 min(3, 2)，可以分组循环字符串，记录前一组的个数，累加二者最小值即可。

代码


/**
 * @date 2026-02-24 16:14
 */
public class CountBinarySubstrings696 {

    public int countBinarySubstrings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int preCnt = 0;
        int i = 0;
        int res = 0;
        while (i < n) {
            int start = i;
            while (i < n && chars[start] == chars[i]) {
                i++;
            }
            int cnt = i - start;
            res += Math.min(preCnt, cnt);
            preCnt = cnt;
        }
        return res;
    }

}

性能

401.二进制手表

目标

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

  • 例如，下面的二进制手表读取 "4:51" 。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

  • 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。

分钟必须由两位数组成，可能会以零开头：

  • 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

示例 1：

输入：turnedOn = 1
输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

示例 2：

输入：turnedOn = 9
输出：[]

说明：

  • 0 <= turnedOn <= 10

思路

有一个二进制手表，用 4 bit 表示小时， 6 bit 代表分钟。已知 bit 位为 1 的数量 turnedOn，返回所有可能的时间。

将数字按照置位数量分组，枚举不同的划分即可。

代码


/**
 * @date 2026-02-24 17:34
 */
public class ReadBinaryWatch401 {

    public List<String> readBinaryWatch(int turnedOn) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < 60; i++) {
            int bc = Integer.bitCount(i);
            map.putIfAbsent(bc, new ArrayList<>());
            map.get(bc).add(i);
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            List<Integer> hours = map.get(i);
            for (Integer h : hours) {
                if (h > 11) {
                    break;
                }
                List<Integer> minutes = map.get(turnedOn - i);
                if (minutes == null) {
                    continue;
                }
                for (Integer m : minutes) {
                    res.add(h + ":" + ((m < 10) ? "0" : "") + m);
                }
            }
        }
        return res;
    }
}

性能

3713.最长的平衡子串I

目标

给你一个由小写英文字母组成的字符串 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;
    }
}

性能

3010.将数组分成最小总代价的子数组I

目标

给你一个长度为 n 的整数数组 nums 。

一个数组的 代价 是它的 第一个 元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。

你需要将 nums 分成 3 个 连续且没有交集 的子数组。

请你返回这些子数组的 最小 代价 总和 。

示例 1：

输入：nums = [1,2,3,12]
输出：6
解释：最佳分割成 3 个子数组的方案是：[1] ，[2] 和 [3,12] ，总代价为 1 + 2 + 3 = 6 。
其他得到 3 个子数组的方案是：
- [1] ，[2,3] 和 [12] ，总代价是 1 + 2 + 12 = 15 。
- [1,2] ，[3] 和 [12] ，总代价是 1 + 3 + 12 = 16 。

示例 2：

输入：nums = [5,4,3]
输出：12
解释：最佳分割成 3 个子数组的方案是：[5] ，[4] 和 [3] ，总代价为 5 + 4 + 3 = 12 。
12 是所有分割方案里的最小总代价。

示例 3：

输入：nums = [10,3,1,1]
输出：12
解释：最佳分割成 3 个子数组的方案是：[10,3] ，[1] 和 [1] ，总代价为 10 + 1 + 1 = 12 。
12 是所有分割方案里的最小总代价。

说明：

  • 3 <= n <= 50
  • 1 <= nums[i] <= 50

思路

定义数组的代价是其第一个元素值，有一个数组 nums，将其分割成 3 个连续且不相交子数组，求子数组的最小总代价。

第一个数组的代价是固定的，问题变成从 1 ~ n -1 选两个最小的元素值。可以排序后取前三个元素的和，或者使用双指针记录最小与次小元素。

代码


/**
 * @date 2026-02-02 9:49
 */
public class MinimumCost3010 {

    public int minimumCost(int[] nums) {
        int n = nums.length;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if (nums[i] < min1) {
                min2 = min1;
                min1 = nums[i];
            } else if (nums[i] < min2) {
                min2 = nums[i];
            }
        }
        return nums[0] + min1 + min2;
    }
}

性能