标签： hard

目标

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

• 每个子字符串的长度 至少 为 k 。
• 每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

示例 1 ：

输入：s = "abaccdbbd", k = 3
输出：2
解释：可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。

示例 2 ：

输入：s = "adbcda", k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。

说明：

• 1 <= k <= s.length <= 2000
• s 仅由小写英文字母组成

思路

返回字符串 s 中长度 至少 为 k 的不重叠回文子串的最大个数。

定义 dp[i] 表示 s[i, n - 1] 中长度为 k 的不重叠回文子串的最大数目，

• 如果不选 s[i]，dp[i] = dp[i + 1]
• 如果选择 s[i]，枚举终点 j，使得 j - i + 1 >= k，如果 s[i, j] 是回文，dp[i] = max(dp[i], 1 + dp[j + 1]))

需要快速判断子串是否是回文，可以预处理。

代码

/**
 * @date 2026-09-15 9:24
 */
public class MaxPalindromes2472 {

    public int maxPalindromes(String s, int k) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                isPalindrome[l--][r++] = true;
            }
            l = i - 1;
            r = i;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                isPalindrome[l--][r++] = true;
            }
        }
        int[] dp = new int[n + 1];
        for (int i = n - k; i >= 0; i--) {
            dp[i] = dp[i + 1];
            for (int j = n - 1; j >= i + k - 1; j--) {
                if (isPalindrome[i][j]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j + 1]);
                }
            }
        }
        return dp[0];
    }

}

性能

目标

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

说明：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

思路

返回字符串 s 不重复的非空子序列的个数。

定义 dp[i + 1][j] 表示 [0, i] 中以字母 j 结尾的子序列个数。使用当前字母作为子序列右端点的方案数为 1 + Σdp[i][j]，即 当前字母自身 加上 与之前的方案拼接。其它右端点的方案数与之前方案数相同 dp[i + 1][j] = dp[i][j]。

代码

/**
 * @date 2026-09-08 14:54
 */
public class DistinctSubseqII940 {

    public int distinctSubseqII(String s) {
        int n = s.length();
        int MOD = 1000000007;
        int[][] dp = new int[n + 1][26];
        for (int i = 0; i < n; i++) {
            int sum = 0;
            int c = s.charAt(i) - 'a';
            for (int j = 0; j < 26; j++) {
                dp[i + 1][j] = dp[i][j];
                sum = (sum + dp[i][j]) % MOD;
            }
            dp[i + 1][c] = 1 + sum;
        }
        int res = 0;
        for (int num : dp[n]) {
            res = (res + num) % MOD;
        }
        return res;
    }
}

性能

目标

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

说明：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

思路

有两个字符串 s 和 t，返回 s 的子序列中 t 的出现个数。

定义 dp[i][j] 表示 s[i, s.length - 1] 中 t[j, t.length - 1] 的子序列个数。dp[i][j] = (s[i] == t[j] ? dp[i + 1][j + 1] : 0) + dp[i + 1][j]。t 为空串时，初始化 dp[i][tl] = 1。

代码

/**
 * @date 2026-09-07 10:32
 */
public class NumDistinct115 {

    public int numDistinct(String s, String t) {
        int sl = s.length();
        int tl = t.length();
        char[] scs = s.toCharArray();
        char[] tcs = t.toCharArray();
        int[][] dp = new int[sl + 1][tl + 1];
        for (int i = 0; i <= sl; i++) {
            dp[i][tl] = 1;
        }
        for (int i = sl - 1; i >= 0; i--) {
            for (int j = tl - 1; j >= 0; j--) {
                dp[i][j] = (scs[i] == tcs[j] ? dp[i + 1][j + 1] : 0) + dp[i + 1][j];
            }
        }
        return dp[0][0];
    }

}

性能

目标

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

说明：

• 1 <= stoneValue.length <= 5 * 10^4
• -1000 <= stoneValue[i] <= 1000

思路

几堆石子排成一排，stoneValue[i] 表示第 i 堆石子的个数。Alice 与 Bob 轮流取石子，Alice 先取，每次可以从剩余的石子堆中取走前 1、2 或者 3 堆石子，直到石子均被取走。返回结束时取走石子最多的玩家姓名，如果相同则返回 Tie。

定义 dp[i] 表示剩余 [i, n - 1] 堆石子，先手与后手所能获得的石子个数之差的最大值。dp[i] = max(sumj - dp[j + 1])，其中 j ∈ [i, min(i + 2, n - 1)]，sumj 表示 [i, j] 的石子堆数量之和。倒序遍历，初始化 dp[n] = 0, dp[n - 1] = stoneValue[n - 1]。

代码

/**
 * @date 2026-08-03 15:22
 */
public class StoneGameIII1406 {

    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[n] = 0;
        dp[n - 1] = stoneValue[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            int sum = 0;
            for (int j = i; j < Math.min(n, i + 3); j++) {
                sum += stoneValue[j];
                dp[i] = Math.max(dp[i], sum - dp[j + 1]);
            }
        }
        if (dp[0] == 0) {
            return "Tie";
        }
        return dp[0] > 0 ? "Alice" : "Bob";
    }
}

性能