当前位置：首页 > news >正文

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

news 2026/6/21 5:48:36

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

参考 doocs/leetcode 官方题解，提供两种 Python3 实现方案：

---

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

```python
from typing import List
from itertools import accumulate

class Solution:
def possibleStringCount(self, word: str, k: int) -> int:
mod = 10**9 + 7
nums = [] # 每组可额外选择的字符数
ans = 1 # 总方案数（无长度限制）
cur = 0 # 当前组长度

for i, c in enumerate(word):
cur += 1
# 遇到组边界
if i == len(word) - 1 or c != word[i + 1]:
if cur > 1:
if k > 0:
nums.append(cur - 1) # 可额外删除 cur-1 个
ans = ans * cur % mod # 该组有 cur 种选择
cur = 0
k -= 1 # 每组至少选一个，k 减少

# 如果 k <= 0，说明每组至少选一个已经满足长度要求
if k < 1:
return ans

m = len(nums)
# f[i][j] 表示前 i 组中，额外选择 j 个字符的方案数
f = [[0] * k for _ in range(m + 1)]
f[0][0] = 1

for i, x in enumerate(nums, 1):
# 前缀和：s[j] = sum(f[i-1][0..j-1])
s = list(accumulate(f[i - 1], initial=0))
for j in range(k):
# f[i][j] = sum(f[i-1][j-x] ... f[i-1][j])
# 用前缀和优化：s[j+1] - s[max(0, j-x)]
l = max(0, j - x)
f[i][j] = (s[j + 1] - s[l] + mod) % mod

# 计算长度小于 k 的方案数（额外选择少于 k 个字符）
invalid = sum(f[m][j] for j in range(k)) % mod

# 答案 = 总方案数 - 长度小于 k 的方案数
return (ans - invalid) % mod
```

---

方法二：滑动窗口优化（空间优化至 O(k)）

```python
from typing import List
from collections import deque

class Solution:
def possibleStringCount(self, word: str, k: int) -> int:
mod = 10**9 + 7

# 获取连续相同字符的分组长度
def get_groups(s: str) -> List[int]:
groups = []
cnt = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
cnt += 1
else:
groups.append(cnt)
cnt = 1
groups.append(cnt)
return groups

groups = get_groups(word)

# 总方案数（无长度限制）：每组长度相乘
total = 1
for g in groups:
total = total * g % mod

# 如果组数 >= k，任何字符串长度都至少为 k
if k <= len(groups):
return total

# 需要额外选择的字符数
need = k - len(groups)

# dp[j] 表示使用已处理组，额外选择 j 个字符的方案数
dp = [0] * need
dp[0] = 1 # 基础情况

for g in groups:
new_dp = [0] * need
window_sum = 0
# 滑动窗口：窗口大小为 g（该组可额外选择的字符数）
for j in range(need):
new_dp[j] = window_sum
window_sum = (window_sum + dp[j]) % mod
# 维护窗口大小
if j >= g - 1:
window_sum = (window_sum - dp[j - (g - 1)] + mod) % mod

dp = new_dp

# 计算无效方案数（长度小于 k）
invalid = sum(dp) % mod

return (total - invalid) % mod
```