LeetCode 3333. 找到初始输入字符串 II — Java 实现参考 doocs/leetcode 官方题解 和 walkccc.me 的滑动窗口优化实现 提供两种 Java 实现方案---方法一动态规划 前缀和官方题解推荐javaimport java.util.ArrayList;import java.util.List;class Solution {public int possibleStringCount(String word, int k) {final int mod (int) 1e9 7;ListInteger nums new ArrayList();long ans 1;int cur 0;int n word.length();// 将连续相同字符分组统计每组长度for (int i 0; i n; i) {cur;if (i n - 1 || word.charAt(i) ! word.charAt(i 1)) {if (cur 1) {if (k 0) {nums.add(cur - 1); // 每组可额外删除的字符数}ans ans * cur % mod; // 总方案数无长度限制}cur 0;k--; // 每组至少选一个字符k 减少}}// 如果 k 0说明每组至少选一个已经满足长度要求if (k 1) {return (int) ans;}int m nums.size();// f[i][j] 表示前 i 组中额外选择 j 个字符的方案数int[][] f new int[m 1][k];f[0][0] 1;for (int i 1; i m; i) {int x nums.get(i - 1); // 第 i 组可额外选择的字符数long[] s new long[k 1];// 前缀和优化for (int j 0; j k; j) {s[j 1] (s[j] f[i - 1][j]) % mod;}for (int j 0; j k; j) {int l Math.max(0, j - x);// f[i][j] sum(f[i-1][j-x] ... f[i-1][j])f[i][j] (int) ((s[j 1] - s[l] mod) % mod);}}// 计算长度小于 k 的方案数额外选择少于 k 个字符long sum 0;for (int j 0; j k; j) {sum (sum f[m][j]) % mod;}// 答案 总方案数 - 长度小于 k 的方案数return (int) ((ans - sum mod) % mod);}}---方法二滑动窗口优化 DP空间优化至 O(k)javaimport java.util.ArrayList;import java.util.List;class Solution {private static final int MOD 1_000_000_007;public int possibleStringCount(String word, int k) {ListInteger groups getConsecutiveLetters(word);// 总方案数无长度限制每组长度相乘long totalCombinations 1;for (int group : groups) {totalCombinations totalCombinations * group % MOD;}// 如果组数 k任何字符串长度都至少为 kif (k groups.size()) {return (int) totalCombinations;}// dp[j] 表示使用已处理组额外选择 j 个字符的方案数int[] dp new int[k];dp[0] 1; // 基础情况空字符串for (int i 0; i groups.size(); i) {int[] newDp new int[k];int windowSum 0;int group groups.get(i);// 滑动窗口j 至少为 i前 i 组每组至少额外选 0 个for (int j i; j k; j) {newDp[j] (newDp[j] windowSum) % MOD;windowSum (windowSum dp[j]) % MOD;// 维护窗口大小为 groupif (j group) {windowSum (windowSum - dp[j - group] MOD) % MOD;}}dp newDp;}// 计算无效方案数长度小于 klong invalidCombinations 0;for (int count : dp) {invalidCombinations (invalidCombinations count) % MOD;}return (int) ((totalCombinations - invalidCombinations MOD) % MOD);}// 返回连续相同字符的分组长度// e.g. aabbbc - [2, 3, 1]private ListInteger getConsecutiveLetters(String word) {ListInteger groups new ArrayList();int group 1;for (int i 1; i word.length(); i) {if (word.charAt(i) word.charAt(i - 1)) {group;} else {groups.add(group);group 1;}}groups.add(group);return groups;}}---核心思路1. 分组统计将连续相同字符分组例如 aabbccdd → [2,2,2,2]。每组至少保留 1 个字符可额外保留 0 到 group-1 个。2. 总方案数无长度限制时每组有 group 种选择保留 1 到 group 个总方案数为各组长度乘积。3. 长度约束要求最终字符串长度 ≥ k。- 先每组至少选 1 个消耗 groups.size() 个字符。- 剩余需要 k - groups.size() 个额外字符。- 用 DP 计算额外选择少于 k - groups.size() 个字符的方案数从总数中减去。4. DP 优化- 前缀和f[i][j] sum(f[i-1][j-x] ... f[i-1][j])用前缀和 O(1) 计算区间和。- 滑动窗口维护大小为 group 的窗口空间优化至 O(k)。复杂度分析方法 时间复杂度 空间复杂度前缀和 DP O(n m×k) O(m×k)滑动窗口 DP O(n m×k) O(k)其中 m 为分组数m ≤ nk ≤ 2000。两种方法均可通过滑动窗口版本空间更优。