标签： medium

目标

给你一个字符串 s 。它可能包含任意数量的 '' 字符。你的任务是删除所有的 '' 字符。

当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：

• 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。

请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。

示例 1：

输入：s = "aaba*"
输出："aab"
解释：
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。

示例 2：

输入：s = "abc"
输出："abc"
解释：
字符串中没有 '*' 字符。

说明：

• 1 <= s.length <= 10^5
• s 只含有小写英文字母和 '*' 字符。
• 输入保证操作可以删除所有的 '*' 字符。

思路

有一个包含任意数量 * 的字符串，每次操作可以删掉 * 以及它左侧的一个字典序最小的字符，如果有多个可以，删除任意一个。求删除所有 * 之后能够得到的 字典序最小的字符串。

贪心算法，优先删除左侧字典序最小且下标最大的字符即可。

代码

/**
 * @date 2025-06-07 9:37
 */
public class ClearStars3170 {

    public String clearStars(String s) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return b[1] - a[1];
        });
        char[] chars = s.toCharArray();
        int n = chars.length;
        for (int i = 0; i < n; i++) {
            char c = chars[i];
            if (c != '*') {
                q.offer(new int[]{c, i});
            } else {
                q.poll();
            }
        }
        char[] res = new char[q.size()];
        PriorityQueue<int[]> tmp = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        tmp.addAll(q);
        int i = 0;
        while (!tmp.isEmpty()) {
            int[] c = tmp.poll();
            res[i++] = (char) c[0];
        }
        return new String(res);
    }
}

性能

目标

给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

• 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
• 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。

请你返回纸上能写出的字典序最小的字符串。

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。

示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。

示例 3：

输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="bdda" ，t="" 。
执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。

说明：

• 1 <= s.length <= 10^5
• s 只包含小写英文字母。

思路

• 首先统计字符串中的字符个数，要使输出的字典序最小，那么第一个字符一定是字符串中出现过的字典序最小的字符
• 为了将该字符打印到首位，需要先定位到这个字符，它前面的字符都会被暂存到栈中
• 确定了第一个字典序最小的字符之后，下一个字符有两个选择，取栈顶字符，或者找到剩下的字符中的字典序最小的

需要维护剩余字符中最小字典序的字符，可以使用有序集合或者后缀。

代码

/**
 * @date 2025-06-06 8:47
 */
public class RobotWithString2434 {

    public String robotWithString(String s) {
        TreeMap<Character, Integer> map = new TreeMap<>();
        char[] chars = s.toCharArray();
        int n = chars.length;
        for (char c : chars) {
            map.merge(c, 1, Integer::sum);
        }
        ArrayDeque<Character> q = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < n) {
            Character min = map.firstKey();
            while (i < n && chars[i] != min) {
                char c = chars[i++];
                q.offer(c);
                map.merge(c, -1, Integer::sum);
                if (map.get(c) == 0) {
                    map.remove(c);
                }
            }
            sb.append(min);
            map.merge(min, -1, Integer::sum);
            if (map.get(min) == 0) {
                map.remove(min);
            }
            i++;
            while (!q.isEmpty() && (map.size() == 0 || q.peekLast() <= map.firstKey())) {
                sb.append(q.pollLast());
            }
        }
        return sb.toString();
    }

}

性能

目标

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

说明：

• 1 <= n <= 10^6
• 1 <= limit <= 10^6

思路

将 n 颗糖果分给 3 位小朋友，每个小朋友分到的糖果数量不超过 limit，求分配的方案数。注意，糖果必须分完，比如示例 1，不存在分得糖果数量为 0 的情况。

• 第一个小朋友分到的糖果数为 a ∈ [0, Math.min(n, limit)]
• 第二个小朋友分到的糖果数为 b ∈ [Math.max(0, n - a - limit), Math.min(n - a, limit)]
• 第三个小朋友分到的糖果数为 n - a - b

代码

/**
 * @date 2025-06-01 21:49
 */
public class DistributeCandies2929 {

    public long distributeCandies(int n, int limit) {
        long res = 0L;
        for (int i = 0; i <= Math.min(n, limit); i++) {
            if (n - i > 2 * limit) {
                continue;
            }
            res += Math.min(n - i, limit) - Math.max(0, n - i - limit) + 1;
        }
        return res;
    }
}

性能

目标

给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。

请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。

请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。

回文串 指的是从前往后和从后往前读一样的字符串。

示例 1：

输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。

示例 2：

输入：words = ["ab","ty","yt","lc","cl","ab"]
输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。

示例 3：

输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。

说明：

• 1 <= words.length <= 10^5
• words[i].length == 2
• words[i] 仅包含小写英文字母。

思路

有一个字符串数组 words，其元素字符个数为 2，求从中选择任意元素组成回文串的最大长度。

统计每个元素的出现次数，如果数组元素的两个字符不同，要组成回文只能左右对称，计算对称的元素对数 cnt，长度为 cnt * 4。如果元素的两个字符相同，它可以全部放到中间，为了使回文最长，当出现更长的相同字符元素时，可以将原来放中间的个数 centerCnt，放到对称的两边，centerCnt / 2 * 4。

代码

/**
 * @date 2025-05-25 1:03
 */
public class LongestPalindrome2131 {

    public int longestPalindrome(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            char a = word.charAt(0);
            char b = word.charAt(1);
            map.merge(a + String.valueOf(b), 1, Integer::sum);
        }
        int res = 0;
        int centerCnt = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            char a = key.charAt(0);
            char b = key.charAt(1);
            if (a == b) {
                Integer cnt = entry.getValue();
                if (cnt % 2 == 1) {
                    res += centerCnt / 2 * 4;
                    centerCnt = cnt;
                } else {
                    res += cnt / 2 * 4;
                }
            } else {
                int cnt = Math.min(entry.getValue(), map.getOrDefault(b + String.valueOf(a), 0));
                res += cnt * 4;
            }
            entry.setValue(0);
        }
        return res + centerCnt * 2;
    }

}

性能