Hard

题目描述

Alice 正在尝试在她的电脑上输入一个特定的字符串。然而，她往往比较笨拙，可能会按键太久，导致一个字符被输入多次。

给你一个字符串 word，它表示 Alice 屏幕上显示的最终输出。你还得到一个正整数 k。

如果 Alice 试图输入一个长度至少为 k 的字符串，请返回她可能打算输入的原始字符串的总数。

由于答案可能很大，请返回对 10^9 + 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 * 10^5
  • word 只包含小写英文字母
  • 1 <= k <= 2000

提示：

  • 与其解决至少 k 长度的问题，我们能否解决最多 k - 1 长度的问题？

解题思路

这是一道动态规划题目。我们需要理解题意：Alice 在输入时可能按键过久导致字符重复，给定最终显示的字符串，求她原本想输入的长度至少为 k 的字符串有多少种。

核心思路：

  1. 分组处理：首先将连续相同的字符分组，记录每组的字符和长度。例如 “aabbccdd” 分为 [‘a’,2], [‘b’,2], [‘c’,2], [’d’,2]。

  2. 正难则反：直接计算长度至少为 k 的情况比较复杂，我们可以先计算总的可能数，再减去长度小于 k 的情况数。

  3. 动态规划：设 dp[i][j] 表示考虑前 i 组字符，长度为 j 的方案数。对于第 i 组字符（长度为 cnt[i]），我们可以选择保留 1 到 cnt[i] 个字符。

  4. 前缀和优化：使用前缀和优化转移过程，避免重复计算。

状态转移：

  • dp[i][j] = sum(dp[i-1][j-t]) 其中 t 从 1 到 min(cnt[i], j)
  • 使用前缀和可以将转移优化到 O(1)

最终答案： 总方案数 - 长度小于 k 的方案数

代码实现

class Solution {
public:
    int possibleStringCount(string word, int k) {
        const int MOD = 1e9 + 7;
        int n = word.length();
        
        // 分组统计连续相同字符
        vector<int> groups;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && word[j] == word[i]) j++;
            groups.push_back(j - i);
            i = j;
        }
        
        int m = groups.size();
        long long total = 1;
        for (int cnt : groups) {
            total = (total * cnt) % MOD;
        }
        
        if (k <= m) return total;
        
        // dp[i][j] = 考虑前i组，总长度为j的方案数
        vector<vector<long long>> dp(m + 1, vector<long long>(k, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= m; i++) {
            vector<long long> prefix(k + 1, 0);
            for (int j = 0; j < k; j++) {
                prefix[j + 1] = (prefix[j] + dp[i - 1][j]) % MOD;
            }
            
            for (int j = 1; j < k; j++) {
                int maxTake = min(groups[i - 1], j);
                dp[i][j] = (prefix[j] - prefix[j - maxTake] + MOD) % MOD;
            }
        }
        
        long long invalid = 0;
        for (int j = m; j < k; j++) {
            invalid = (invalid + dp[m][j]) % MOD;
        }
        
        return (total - invalid + MOD) % MOD;
    }
};

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(word)
        
        # 分组统计连续相同字符
        groups = []
        i = 0
        while i < n:
            j = i
            while j < n and word[j] == word[i]:
                j += 1
            groups.append(j - i)
            i = j
        
        m = len(groups)
        total = 1
        for cnt in groups:
            total = (total * cnt) % MOD
        
        if k <= m:
            return total
        
        # dp[i][j] = 考虑前i组，总长度为j的方案数
        dp = [[0] * k for _ in range(m + 1)]
        dp[0][0] = 1
        
        for i in range(1, m + 1):
            prefix = [0] * (k + 1)
            for j in range(k):
                prefix[j + 1] = (prefix[j] + dp[i - 1][j]) % MOD
            
            for j in range(1, k):
                max_take = min(groups[i - 1], j)
                dp[i][j] = (prefix[j] - prefix[j - max_take]) % MOD
        
        invalid = sum(dp[m][j] for j in range(m, k)) % MOD
        return (total - invalid) % MOD

public class Solution {
    public int PossibleStringCount(string word, int k) {
        const int MOD = 1000000007;
        int n = word.Length;
        
        // 分组统计连续相同字符
        List<int> groups = new List<int>();
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && word[j] == word[i]) j++;
            groups.Add(j - i);
            i = j;
        }
        
        int m = groups.Count;
        long total = 1;
        foreach (int cnt in groups) {
            total = (total * cnt) % MOD;
        }
        
        if (k <= m) return (int)total;
        
        // dp[i][j] = 考虑前i组，总长度为j的方案数
        long[,] dp = new long[m + 1, k];
        dp[0, 0] = 1;
        
        for (int idx = 1; idx <= m; idx++) {
            long[] prefix = new long[k + 1];
            for (int j = 0; j < k; j++) {
                prefix[j + 1] = (prefix[j] + dp[idx - 1, j]) % MOD;
            }
            
            for (int j = 1; j < k; j++) {
                int maxTake = Math.Min(groups[idx - 1], j);
                dp[idx, j] = (prefix[j] - prefix[j - maxTake] + MOD) % MOD;
            }
        }
        
        long invalid = 0;
        for (int j = m; j < k; j++) {
            invalid = (invalid + dp[m, j]) % MOD;
        }
        
        return (int)((total - invalid + MOD) % MOD);
    }
}

var possibleStringCount = function(word, k) {
    const MOD = 1e9 + 7;
    const n = word.length;
    
    // 分组统计连续相同字符
    const groups = [];
    let i = 0;
    while (i < n) {
        let j = i;
        while (j < n && word[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(mk)
空间复杂度O(mk)

其中 m 为连续字符组的数量（最多为字符串长度 n），k 为给定的最小长度限制。

相关题目