Kimi LeetCode 3333. 找到初始输入字符串 II Java实现

2026/6/21 16:04:27

LeetCode 3333. 找到初始输入字符串 II — Java 实现

参考 doocs/leetcode 官方题解和 walkccc.me 的滑动窗口优化实现，提供两种 Java 实现方案：

---

方法一：动态规划 + 前缀和（官方题解，推荐）

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
public int possibleStringCount(String word, int k) {
final int mod = (int) 1e9 + 7;
List<Integer> 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)）

```java
import 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) {
List<Integer> groups = getConsecutiveLetters(word);

// 总方案数（无长度限制）：每组长度相乘
long totalCombinations = 1;
for (int group : groups) {
totalCombinations = totalCombinations * group % MOD;
}

// 如果组数 >= k，任何字符串长度都至少为 k
if (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;
// 维护窗口大小为 group
if (j >= group) {
windowSum = (windowSum - dp[j - group] + MOD) % MOD;
}
}
dp = newDp;
}

// 计算无效方案数（长度小于 k）
long invalidCombinations = 0;
for (int count : dp) {
invalidCombinations = (invalidCombinations + count) % MOD;
}

return (int) ((totalCombinations - invalidCombinations + MOD) % MOD);
}

// 返回连续相同字符的分组长度
// e.g. "aabbbc" -> [2, 3, 1]
private List<Integer> getConsecutiveLetters(String word) {
List<Integer> 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;
}
}
```