标签： 计数

目标

给你一个 回文 字符串 s。

返回 s 的按字典序排列的 最小 回文排列。

如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。

排列 是字符串中所有字符的重排。

如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。

如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。

示例 1：

输入： s = "z"
输出： "z"
解释：
仅由一个字符组成的字符串已经是按字典序最小的回文。

示例 2：

输入： s = "babab"
输出： "abbba"
解释：
通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。

示例 3：

输入： s = "daccad"
输出： "acddca"
解释：
通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。

说明：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成。
• 保证 s 是回文字符串。

思路

有一个回文字符串 s，将其重新排列成回文字符串，使得字典序最小。

记录字符串中字符的出现次数，然后按字典序从两边向中间填充，如果出现次数为奇数，那么该字符为中间元素。

代码

/**
 * @date 2026-07-28 9:03
 */
public class SmallestPalindrome3517 {

    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        char[] res = new char[n];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        char mid = 0;
        int cur = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                mid = (char) ('a' + i);
            }
            int k = cnt[i] / 2;
            char c = (char) ('a' + i);
            for (int j = 0; j < k; j++) {
                res[cur + j] = c;
                res[n - cur - j - 1] = c;
            }
            cur += k;
        }
        if (n % 2 == 1) {
            res[n / 2] = mid;
        }
        return new String(res);
    }

}

性能

目标

给你一个长度为 n 的二进制字符串 s，其中：

• '1' 表示一个 活跃 区段。
• '0' 表示一个 非活跃 区段。

你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：

• 将一个被 '0' 包围的连续 '1' 区块转换为全 '0'。
• 然后，将一个被 '1' 包围的连续 '0' 区块转换为全 '1'。

返回在执行最优操作后，s 中的 最大 活跃区段数。

注意：处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。

示例 1：

输入： s = "01"
输出： 1
解释：
因为没有被 '0' 包围的 '1' 区块，因此无法进行有效操作。最大活跃区段数为 1。

示例 2：

输入： s = "0100"
输出： 4
解释：
字符串 "0100" → 两端加上 '1' 后得到 "101001" 。
选择 "0100"，"101001" → "100001" → "111111" 。
最终的字符串去掉两端的 '1' 后为 "1111" 。最大活跃区段数为 4。

示例 3：

输入： s = "1000100"
输出： 7
解释：
字符串 "1000100" → 两端加上 '1' 后得到 "110001001" 。
选择 "000100"，"110001001" → "110000001" → "111111111"。
最终的字符串去掉两端的 '1' 后为 "1111111"。最大活跃区段数为 7。

示例 4：

输入： s = "01010"
输出： 4
解释：
字符串 "01010" → 两端加上 '1' 后得到 "1010101"。
选择 "010"，"1010101" → "1000101" → "1111101"。
最终的字符串去掉两端的 '1' 后为 "11110"。最大活跃区段数为 4。

说明：

• 1 <= n == s.length <= 10^5
• s[i] 仅包含 '0' 或 '1'

思路

有一个二进制字符串，在其首尾拼上 1，然后执行一次操作：将一个被 0 包围的连续 1 全部转为 0，然后将一个被 1 包围的连续 0 全部转为 1，求操作之后 字符串 中 1 的最大个数（不包括首尾拼接的 1）。

实际上是求字符串中 1 两侧连续 0 的最大长度。

判断 01 分界，记录之前连续 0 的个数与当前连续 0 的个数之和的最大值。

代码

/**
 * @date 2026-07-21 10:41
 */
public class MaxActiveSectionsAfterTrade3499 {

    public int maxActiveSectionsAfterTrade(String s) {
        int n = s.length();
        int prevZero = 0;
        int curZero = 0;
        int oneCnt = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                oneCnt++;
                if (curZero > 0) {
                    if (prevZero > 0) {
                        max = Math.max(max, curZero + prevZero);
                    }
                    prevZero = curZero;
                    curZero = 0;
                }
            } else {
                curZero++;
            }
        }
        if (curZero > 0) {
            if (prevZero > 0) {
                max = Math.max(max, curZero + prevZero);
            }
        }
        return oneCnt + max;
    }

}

性能

目标

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。

示例 3：

输入：s = "abc"
输出：1

说明：

• 3 <= s.length <= 5 x 10^4
• s 只包含字符 a，b 和 c 。

思路

有一个字符串只包含三个字符 a b c，求这三个字符至少出现一次的子串个数。

直接的想法是计算这三个字符出现次数的前缀和，然后使用滑动窗口。使用前缀和来判断窗口内的子串是否满足条件，如果 [l, r] 满足条件，那么 [l, r ~ n - 1] 也满足条件。

判断字符是否至少出现一次可以不用前缀和，使用三个变量记录它们上次出现的下标，如果小于左端点则用 -1 标记。

代码

/**
 * @date 2026-06-30 9:14
 */
public class NumberOfSubstrings1358 {

    public int numberOfSubstrings(String s) {
        int n = s.length();
        int a = -1, b = -1, c = -1;
        int l = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a') {
                a = i;
            } else if (s.charAt(i) == 'b') {
                b = i;
            } else {
                c = i;
            }
            while (a >= 0 && b >= 0 && c >= 0) {
                res += n - i;
                if (a <= l) {
                    a = -1;
                } else if (b <= l) {
                    b = -1;
                } else if (c <= l) {
                    c = -1;
                }
                l++;
            }
        }
        return res;
    }

}

性能

目标

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

注意：Tony 可以按任意顺序购买雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

你必须使用计数排序解决此问题。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

说明：

• costs.length == n
• 1 <= n <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= coins <= 10^8

思路

costs[i] 表示第 i 支雪糕的数量，求使用现金 coins 所能购买雪糕的最大数量。

贪心策略：优先购买价格较低的雪糕。使用计数排序记录每种价格的雪糕数量，从小到大遍历价格，累加当前所能购买的雪糕数量，如果超过剩余金额直接返回。

代码

/**
 * @date 2026-06-22 9:27
 */
public class MaxIceCream1833 {

    public int maxIceCream_v1(int[] costs, int coins) {
        int max = 0;
        for (int cost : costs) {
            max = Math.max(max, cost);
        }
        int[] cnt = new int[max + 1];
        for (int cost : costs) {
            cnt[cost]++;
        }
        int res = 0;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            if (coins < i) {
                return res;
            }
            int amount = Math.min(coins / i, cnt[i]);
            coins -= amount * i;
            res += amount;
        }
        return res;
    }

}

性能

目标

给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且 每个 小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个 特殊字母 。

返回 word 中 特殊字母 的数量。

示例 1:

输入：word = "aaAbcBC"
输出：3
解释：
特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = "abc"
输出：0
解释：
word 中不存在特殊字母。

示例 3:

输入：word = "AbBCab"
输出：0
解释：
word 中不存在特殊字母。

说明：

• 1 <= word.length <= 2 * 10^5
• word 仅由小写和大写英文字母组成。

思路

有一个字符串 word，返回其中大小写同时存在，且 所有小写都在其大写之前出现 的的字母个数。

与 3120_统计特殊字母的数量I 相比，本题多了顺序条件。

使用两个数组标记字母（无论大小写，统一用 0 ~ 25 表示）是否被计数以及是否被删除：

• 如果当前字母是大写：
  • 之前大小写都已出现（计数 或者 删除都已经处理过了），直接跳过
  • 对应的小写已经出现，计数（上面的条件保证了不会重复计数），并标记为已计数
• 如果当前字母是小写：
  • 之前大小写都已出现，且已计数（不一定被计数，因为小写可能后出现）未被标记为已删除，则计数减一，并标记为已删除
  • 注意如果之前只出现过大写，不用处理，因为没有被计数

代码

/**
 * @date 2026-05-26 9:06
 */
public class NumberOfSpecialChars3121 {

    /**
     * A(65):  1000001
     * Z(90):  1011010
     * a(97):  1100001
     * z(122): 1111010
     * 31: 0011111
     * 32: 0100000
     */
    public int numberOfSpecialChars_v1(String word) {
        Set<Integer> set = new HashSet<>();
        int n = word.length();
        boolean[] rm = new boolean[26];
        boolean[] add = new boolean[26];
        int res = 0;
        for (int i = 0; i < n; i++) {
            int c = word.charAt(i);
            // 将字母映射到 0 ~ 25，不区分大小写
            int index = (c & 31) - 1;
            // flag 为 0 表示大写字母，为 1 是小写字母
            int flag = c & 32;
            // 如果之前已经遇到过字母的大小写
            if (set.contains(c) && set.contains(c ^ (1 << 5))) {
                // 如果当前是大写，无需处理，因为需要加的话前面已经加了，需要减的前面已经减了
                if (flag == 0){
                    continue;
                }
                // 如果当前是小写，计数过且没减过，计数减一，并标记
                // 注意，如果之前只遇到过大写，不用处理，因为不满足条件没有被计数
                if (!rm[index] && add[index]){
                    rm[index] = true;
                    res--;
                }
            }
            // 如果当前是大写并且之前出现过小写，标记并计数
            if (flag == 0 && set.contains(c + 32)){
                add[index] = true;
                res++;
            }
            set.add(c);
        }
        return res;
    }

}

性能