LeetCode 3333. 找到初始输入字符串 II — Python3 实现参考 doocs/leetcode 官方题解 提供两种 Python3 实现方案---方法一动态规划 前缀和推荐pythonfrom typing import Listfrom itertools import accumulateclass Solution:def possibleStringCount(self, word: str, k: int) - int:mod 10**9 7nums [] # 每组可额外选择的字符数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 0k - 1 # 每组至少选一个k 减少# 如果 k 0说明每组至少选一个已经满足长度要求if k 1:return ansm len(nums)# f[i][j] 表示前 i 组中额外选择 j 个字符的方案数f [[0] * k for _ in range(m 1)]f[0][0] 1for i, x in enumerate(nums, 1):# 前缀和s[j] sum(f[i-1][0..j-1])s list(accumulate(f[i - 1], initial0))for j in range(k):# f[i][j] sum(f[i-1][j-x] ... f[i-1][j])# 用前缀和优化s[j1] - 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)pythonfrom typing import Listfrom collections import dequeclass Solution:def possibleStringCount(self, word: str, k: int) - int:mod 10**9 7# 获取连续相同字符的分组长度def get_groups(s: str) - List[int]:groups []cnt 1for i in range(1, len(s)):if s[i] s[i - 1]:cnt 1else:groups.append(cnt)cnt 1groups.append(cnt)return groupsgroups get_groups(word)# 总方案数无长度限制每组长度相乘total 1for g in groups:total total * g % mod# 如果组数 k任何字符串长度都至少为 kif k len(groups):return total# 需要额外选择的字符数need k - len(groups)# dp[j] 表示使用已处理组额外选择 j 个字符的方案数dp [0] * needdp[0] 1 # 基础情况for g in groups:new_dp [0] * needwindow_sum 0# 滑动窗口窗口大小为 g该组可额外选择的字符数for j in range(need):new_dp[j] window_sumwindow_sum (window_sum dp[j]) % mod# 维护窗口大小if j g - 1:window_sum (window_sum - dp[j - (g - 1)] mod) % moddp new_dp# 计算无效方案数长度小于 kinvalid sum(dp) % modreturn (total - invalid) % mod---核心思路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。两种方法均可通过滑动窗口版本空间更优。
