class Solution {
public:
int possibleStringCount(string word, int k) {
}
};
3333. 找到初始输入字符串 II
Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。
给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。同时给你一个 正 整数 k ，表示一开始 Alice 输入字符串的长度 至少 为 k 。
请你返回 Alice 一开始可能想要输入字符串的总方案数。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：word = "aabbccdd", k = 7
输出：5
解释：
可能的字符串包括："aabbccdd" ，"aabbccd" ，"aabbcdd" ，"aabccdd" 和 "abbccdd" 。
示例 2：
输入：word = "aabbccdd", k = 8
输出：1
解释：
唯一可能的字符串是 "aabbccdd" 。
示例 3：
输入：word = "aaabbb", k = 3
输出：8
提示：
1 <= word.length <= 5 * 105word 只包含小写英文字母。1 <= k <= 2000原站题解
cpp 解法, 执行用时: 222 ms, 内存消耗: 48.8 MB, 提交时间: 2024-11-03 22:15:03
class Solution {
public:
int possibleStringCount1(string word, int k) {
int n = word.length();
if (n < k) { // 无法满足要求
return 0;
}
const int MOD = 1'000'000'007;
vector<int> cnts;
long long ans = 1;
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt++;
if (i == n - 1 || word[i] != word[i + 1]) {
// 如果 cnt = 1，这组字符串必选，无需参与计算
if (cnt > 1) {
if (k > 0) {
cnts.push_back(cnt - 1);
}
ans = ans * cnt % MOD;
}
k--; // 注意这里把 k 减小了
cnt = 0;
}
}
if (k <= 0) {
return ans;
}
int m = cnts.size();
vector<vector<int>> f(m + 1, vector<int>(k));
f[0][0] = 1;
vector<int> s(k + 1);
for (int i = 0; i < m; i++) {
// 计算 f[i] 的前缀和数组 s
for (int j = 0; j < k; j++) {
s[j + 1] = (s[j] + f[i][j]) % MOD;
}
// 计算子数组和
for (int j = 0; j < k; j++) {
f[i + 1][j] = (s[j + 1] - s[max(j - cnts[i], 0)]) % MOD;
}
}
ans -= reduce(f[m].begin(), f[m].end(), 0LL);
return (ans % MOD + MOD) % MOD; // 保证结果非负
}
// 空间优化
int possibleStringCount(string word, int k) {
int n = word.length();
if (n < k) { // 无法满足要求
return 0;
}
const int MOD = 1'000'000'007;
vector<int> cnts;
long long ans = 1;
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt++;
if (i == n - 1 || word[i] != word[i + 1]) {
// 如果 cnt = 1，这组字符串必选，无需参与计算
if (cnt > 1) {
if (k > 0) { // 保证空间复杂度为 O(k)
cnts.push_back(cnt - 1);
}
ans = ans * cnt % MOD;
}
k--; // 注意这里把 k 减小了
cnt = 0;
}
}
if (k <= 0) {
return ans;
}
vector<int> f(k);
f[0] = 1;
for (int c : cnts) {
// 原地计算 f 的前缀和
for (int j = 1; j < k; j++) {
f[j] = (f[j] + f[j - 1]) % MOD;
}
// 计算子数组和
for (int j = k - 1; j > c; j--) {
f[j] = (f[j] - f[j - c - 1]) % MOD;
}
}
ans -= reduce(f.begin(), f.end(), 0LL);
return (ans % MOD + MOD) % MOD; // 保证结果非负
}
};
java 解法, 执行用时: 97 ms, 内存消耗: 47.6 MB, 提交时间: 2024-11-03 22:14:29
class Solution {
public int possibleStringCount1(String word, int k) {
int n = word.length();
if (n < k) { // 无法满足要求
return 0;
}
final int MOD = 1_000_000_007;
List<Integer> cnts = new ArrayList<>();
long ans = 1;
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt++;
if (i == n - 1 || word.charAt(i) != word.charAt(i + 1)) {
// 如果 cnt = 1，这组字符串必选，无需参与计算
if (cnt > 1) {
if (k > 0) {
cnts.add(cnt - 1);
}
ans = ans * cnt % MOD;
}
k--; // 注意这里把 k 减小了
cnt = 0;
}
}
if (k <= 0) {
return (int) ans;
}
int m = cnts.size();
int[][] f = new int[m + 1][k];
f[0][0] = 1;
int[] s = new int[k + 1];
for (int i = 0; i < m; i++) {
// 计算 f[i] 的前缀和数组 s
for (int j = 0; j < k; j++) {
s[j + 1] = (s[j] + f[i][j]) % MOD;
}
int c = cnts.get(i);
// 计算子数组和
for (int j = 0; j < k; j++) {
f[i + 1][j] = (s[j + 1] - s[Math.max(j - c, 0)]) % MOD;
}
}
for (int x : f[m]) {
ans -= x;
}
return (int) ((ans % MOD + MOD) % MOD); // 保证结果非负
}
// 空间优化
public int possibleStringCount(String word, int k) {
int n = word.length();
if (n < k) { // 无法满足要求
return 0;
}
final int MOD = 1_000_000_007;
List<Integer> cnts = new ArrayList<>();
long ans = 1;
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt++;
if (i == n - 1 || word.charAt(i) != word.charAt(i + 1)) {
// 如果 cnt = 1，这组字符串必选，无需参与计算
if (cnt > 1) {
if (k > 0) { // 保证空间复杂度为 O(k)
cnts.add(cnt - 1);
}
ans = ans * cnt % MOD;
}
k--; // 注意这里把 k 减小了
cnt = 0;
}
}
if (k <= 0) {
return (int) ans;
}
int[] f = new int[k];
f[0] = 1;
for (int c : cnts) {
// 原地计算 f 的前缀和
for (int j = 1; j < k; j++) {
f[j] = (f[j] + f[j - 1]) % MOD;
}
// 计算子数组和
for (int j = k - 1; j > c; j--) {
f[j] = (f[j] - f[j - c - 1]) % MOD;
}
}
for (int x : f) {
ans -= x;
}
return (int) ((ans % MOD + MOD) % MOD); // 保证结果非负
}
}
golang 解法, 执行用时: 82 ms, 内存消耗: 9.1 MB, 提交时间: 2024-11-03 22:13:51
func possibleStringCount1(word string, k int) int {
if len(word) < k { // 无法满足要求
return 0
}
const mod = 1_000_000_007
cnts := []int{}
ans := 1
cnt := 0
for i := range word {
cnt++
if i == len(word)-1 || word[i] != word[i+1] {
// 如果 cnt = 1，这组字符串必选，无需参与计算
if cnt > 1 {
if k > 0 {
cnts = append(cnts, cnt-1)
}
ans = ans * cnt % mod
}
k-- // 注意这里把 k 减小了
cnt = 0
}
}
if k <= 0 {
return ans
}
m := len(cnts)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, k)
}
f[0][0] = 1
s := make([]int, k+1)
for i, c := range cnts {
// 计算 f[i] 的前缀和数组 s
for j, v := range f[i] {
s[j+1] = (s[j] + v) % mod
}
// 计算子数组和
for j := range f[i+1] {
f[i+1][j] = s[j+1] - s[max(j-c, 0)]
}
}
for _, v := range f[m] {
ans -= v
}
return (ans%mod + mod) % mod // 保证结果非负
}
// 空间优化
func possibleStringCount(word string, k int) int {
if len(word) < k { // 无法满足要求
return 0
}
const mod = 1_000_000_007
cnts := []int{}
ans := 1
cnt := 0
for i := range word {
cnt++
if i == len(word)-1 || word[i] != word[i+1] {
// 如果 cnt = 1，这组字符串必选，无需参与计算
if cnt > 1 {
if k > 0 { // 保证空间复杂度为 O(k)
cnts = append(cnts, cnt-1)
}
ans = ans * cnt % mod
}
k-- // 注意这里把 k 减小了
cnt = 0
}
}
if k <= 0 {
return ans
}
f := make([]int, k)
f[0] = 1
for _, c := range cnts {
// 原地计算 f 的前缀和
for j := 1; j < k; j++ {
f[j] = (f[j] + f[j-1]) % mod
}
// 计算子数组和
for j := k - 1; j > c; j-- {
f[j] -= f[j-c-1]
}
}
for _, x := range f {
ans -= x
}
return (ans%mod + mod) % mod // 保证结果非负
}
python3 解法, 执行用时: 1358 ms, 内存消耗: 21.2 MB, 提交时间: 2024-11-03 22:13:12
class Solution:
def possibleStringCount1(self, word: str, k: int) -> int:
n = len(word)
if n < k: # 无法满足要求
return 0
MOD = 1_000_000_007
cnts = []
ans = 1
cnt = 0
for i in range(n):
cnt += 1
if i == n - 1 or word[i] != word[i + 1]:
# 如果 cnt = 1，这组字符串必选，无需参与计算
if cnt > 1:
if k > 0:
cnts.append(cnt - 1)
ans = ans * cnt % MOD
k -= 1 # 注意这里把 k 减小了
cnt = 0
if k <= 0:
return ans
f = [[0] * k for _ in range(len(cnts) + 1)]
f[0][0] = 1
for i, c in enumerate(cnts):
# 计算 f[i] 的前缀和数组 s
s = list(accumulate(f[i], initial=0))
# 计算子数组和
for j in range(k):
f[i + 1][j] = (s[j + 1] - s[max(j - c, 0)]) % MOD
return (ans - sum(f[-1])) % MOD
# 空间优化
def possibleStringCount(self, word: str, k: int) -> int:
n = len(word)
if n < k: # 无法满足要求
return 0
MOD = 1_000_000_007
cnts = []
ans = 1
cnt = 0
for i in range(n):
cnt += 1
if i == n - 1 or word[i] != word[i + 1]:
# 如果 cnt = 1，这组字符串必选，无需参与计算
if cnt > 1:
if k > 0: # 保证空间复杂度为 O(k)
cnts.append(cnt - 1)
ans = ans * cnt % MOD
k -= 1 # 注意这里把 k 减小了
cnt = 0
if k <= 0:
return ans
f = [0] * k
f[0] = 1
for c in cnts:
# 原地计算 f 的前缀和
for j in range(1, k):
f[j] = (f[j] + f[j - 1]) % MOD
# 计算子数组和
for j in range(k - 1, c, -1):
f[j] -= f[j - c - 1]
return (ans - sum(f)) % MOD