2025-05-22：找到初始输入字符串Ⅱ 用go语言，Alice 在键盘上输

摘要：分组连续相同字符：• 首先将 word 分成连续的相同字符的组。例如，"aabbccdd" 分为 ["aa", "bb", "cc", "dd"]。• 对于每组，至少保留一个字符，因此每组的选择是保留 1 到 count 个字符（count 是该组字符的原始数

2025-05-22：找到初始输入字符串Ⅱ。用go语言，Alice 在键盘上输入一个字符串，但由于输入时可能按键时间过长，导致某些字符被重复输入多次。

给定一个字符串 word，表示最终显示在屏幕上的内容，同时给定一个正整数 k，表示 Alice 最初打算输入的字符串长度至少为 k。

请你计算，满足这种情况的所有可能的原字符串方案数，并将结果对 1000000007 取模后返回。

word 只包含小写英文字母。

输入：word = "aabbccdd", k = 7。

输出：5。

解释：

可能的字符串包括："aabbccdd" ，"aabbccd" ，"aabbcdd" ，"aabccdd" 和 "abbccdd" 。

题目来自力扣3333。

1. 分组连续相同字符：• 首先将 word 分成连续的相同字符的组。例如，"aabbccdd" 分为 ["aa", "bb", "cc", "dd"]。• 对于每组，至少保留一个字符，因此每组的选择是保留 1 到 count 个字符（count 是该组字符的原始数量）。2. 计算初始方案数：• 对于每组，如果该组的字符数为 c，则可以选择保留 1 到 c 个字符，因此有 c 种选择。• 初始方案数是所有组的 c 的乘积。例如，"aa", "bb", "cc", "dd" 的 c 分别为 2, 2, 2, 2，初始方案数为 2 * 2 * 2 * 2 = 16。• 但我们需要排除那些原字符串长度小于 k 的情况。3. 动态规划计算不满足条件的方案数：• 我们需要计算原字符串长度小于 k 的方案数，然后用初始方案数减去这些不满足条件的方案数。• 设原字符串长度为 total_length，则 total_length 是各组保留字符数的和。• 我们需要计算 total_length • 动态规划：• 定义 f[j] 表示选择前 i 组时，总长度为 j 的方案数。• 初始时 f[0] = 1（不选任何字符的方案数为 1，但实际每组至少选 1 个字符，因此需要调整）。• 对于每组，其字符数为 c，可以选择保留 1 到 c 个字符，因此对动态规划的转移是：• 对于每个 j，f[j] 可以从 f[j - 1], f[j - 2], ..., f[j - c] 转移而来。• 由于每组至少选 1 个字符，因此实际的总长度至少是组的数量（即 m，组数）。• 我们需要计算 m • 具体实现中，可以优化空间复杂度为 O(k)。4. 排除不满足条件的方案数：• 初始方案数为 ans。• 不满足条件的方案数为 sum(f[m..k-1])。• 最终结果为 ans - sum(f[m..k-1])。1. 分组存储：O(m)，但可以优化为 O(1)（无需显式存储所有组）。2. 动态规划数组：O(k)。3. 总空间复杂度：O(k)。

package mainimport ( "fmt")func possibleStringCount(word string, k int)int { iflen(word) 1 { if k > 0 { // 保证空间复杂度为 O(k) cnts = append(cnts, cnt-1) } ans = ans * cnt % mod } k-- // 注意这里把 k 减小了 cnt = 0 } } if k c; j-- { f[j] -= f[j-c-1] } } for _, x := range f { ans -= x } return (ans%mod + mod) % mod // 保证结果非负}func main { word := "aabbccdd" k := 7 result := possibleStringCount(word, k) fmt.Println(result)}

fn possible_string_count(word: &str, k: usize) -> i32 {let mod_val = 1_000_000_007i64;let n = word.len;if n 1 {if kk > 0 {cnts.push(cnt - 1);}ans = ans * (cnt as i64) % mod_val;}kk -= 1;cnt = 0;}}if kk