标签： 枚举

目标

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

说明：

• 1 <= s.length <= 5 * 10^5
• s[i] 不是 '0' 就是 '1'
• 1 <= k <= 20

思路

检查一个二进制字符串是否包含所有长度为 k 的二进制子串。

长度为 k 的二进制子串的个数有 2^k 个，将子串视为二进制数字，使用长度为 k 的滑动窗口，记录窗口内子串表示的数字，判断是否所有数字都出现过即可。将左边界移出窗口需要将左边第一位置零 num = (num & (1 << (k - 1))) ^ num。先提取左边第一位，其余位均为 0，然后与 num 异或即可。

代码

/**
 * @date 2026-02-24 11:31
 */
public class HasAllCodes1461 {

    public boolean hasAllCodes(String s, int k) {
        if (k > 18) {
            return false;
        }
        int n = 1 << k;
        boolean[] visited = new boolean[n];
        int num = 0;
        char[] chars = s.toCharArray();
        int l = 0;
        for (int r = 0; r < chars.length; r++) {
            num = (num << 1) | (chars[r] - '0');
            if (r - l + 1 == k) {
                visited[num] = true;
                num = (num & (1 << (k - 1))) ^ num;
                l++;
            }
        }
        for (boolean b : visited) {
            if (!b) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

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

性能