Welcome to Subscribe On Youtube
3333. Find the Original Typed String II
Description
Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.
You are given a string word
, which represents the final output displayed on Alice's screen. You are also given a positive integer k
.
Return the total number of possible original strings that Alice might have intended to type, if she was trying to type a string of size at least k
.
Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: word = "aabbccdd", k = 7
Output: 5
Explanation:
The possible strings are: "aabbccdd"
, "aabbccd"
, "aabbcdd"
, "aabccdd"
, and "abbccdd"
.
Example 2:
Input: word = "aabbccdd", k = 8
Output: 1
Explanation:
The only possible string is "aabbccdd"
.
Example 3:
Input: word = "aaabbb", k = 3
Output: 8
Constraints:
1 <= word.length <= 5 * 105
word
consists only of lowercase English letters.1 <= k <= 2000
Solutions
Solution 1
-
class Solution { public int possibleStringCount(String word, int k) { final int mod = (int) 1e9 + 7; List<Integer> nums = new ArrayList<>(); long ans = 1; int cur = 0; int n = word.length(); for (int i = 0; i < n; i++) { cur++; if (i == n - 1 || word.charAt(i) != word.charAt(i + 1)) { if (cur > 1) { if (k > 0) { nums.add(cur - 1); } ans = ans * cur % mod; } cur = 0; k--; } } if (k < 1) { return (int) ans; } int m = nums.size(); int[][] f = new int[m + 1][k]; f[0][0] = 1; for (int i = 1; i <= m; i++) { int x = nums.get(i - 1); long[] s = new long[k + 1]; for (int j = 0; j < k; j++) { s[j + 1] = (s[j] + f[i - 1][j]) % mod; } for (int j = 0; j < k; j++) { int l = Math.max(0, j - x); f[i][j] = (int) ((s[j + 1] - s[l] + mod) % mod); } } long sum = 0; for (int j = 0; j < k; j++) { sum = (sum + f[m][j]) % mod; } return (int) ((ans - sum + mod) % mod); } }
-
class Solution { public: int possibleStringCount(string word, int k) { const int mod = 1e9 + 7; vector<int> nums; long long ans = 1; int cur = 0; int n = word.size(); for (int i = 0; i < n; ++i) { cur++; if (i == n - 1 || word[i] != word[i + 1]) { if (cur > 1) { if (k > 0) { nums.push_back(cur - 1); } ans = ans * cur % mod; } cur = 0; k--; } } if (k < 1) { return ans; } int m = nums.size(); vector<vector<int>> f(m + 1, vector<int>(k, 0)); f[0][0] = 1; for (int i = 1; i <= m; ++i) { int x = nums[i - 1]; vector<long long> s(k + 1, 0); for (int j = 0; j < k; ++j) { s[j + 1] = (s[j] + f[i - 1][j]) % mod; } for (int j = 0; j < k; ++j) { int l = max(0, j - x); f[i][j] = (s[j + 1] - s[l] + mod) % mod; } } long long sum = 0; for (int j = 0; j < k; ++j) { sum = (sum + f[m][j]) % mod; } return (ans - sum + mod) % mod; } };
-
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) ans = ans * cur % mod cur = 0 k -= 1 if k < 1: return ans m = len(nums) f = [[0] * k for _ in range(m + 1)] f[0][0] = 1 for i, x in enumerate(nums, 1): s = list(accumulate(f[i - 1], initial=0)) for j in range(k): f[i][j] = (s[j + 1] - s[j - min(x, j)] + mod) % mod return (ans - sum(f[m][j] for j in range(k))) % mod
-
func possibleStringCount(word string, k int) int { const mod = 1_000_000_007 nums := []int{} ans := 1 cur := 0 n := len(word) for i := 0; i < n; i++ { cur++ if i == n-1 || word[i] != word[i+1] { if cur > 1 { if k > 0 { nums = append(nums, cur-1) } ans = ans * cur % mod } cur = 0 k-- } } if k < 1 { return ans } m := len(nums) f := make([][]int, m+1) for i := range f { f[i] = make([]int, k) } f[0][0] = 1 for i := 1; i <= m; i++ { x := nums[i-1] s := make([]int, k+1) for j := 0; j < k; j++ { s[j+1] = (s[j] + f[i-1][j]) % mod } for j := 0; j < k; j++ { l := j - x if l < 0 { l = 0 } f[i][j] = (s[j+1] - s[l] + mod) % mod } } sum := 0 for j := 0; j < k; j++ { sum = (sum + f[m][j]) % mod } return (ans - sum + mod) % mod }
-
function possibleStringCount(word: string, k: number): number { const mod = 1_000_000_007; const nums: number[] = []; let ans = 1; let cur = 0; const n = word.length; for (let i = 0; i < n; i++) { cur++; if (i === n - 1 || word[i] !== word[i + 1]) { if (cur > 1) { if (k > 0) { nums.push(cur - 1); } ans = (ans * cur) % mod; } cur = 0; k--; } } if (k < 1) { return ans; } const m = nums.length; const f: number[][] = Array.from({ length: m + 1 }, () => Array(k).fill(0)); f[0][0] = 1; for (let i = 1; i <= m; i++) { const x = nums[i - 1]; const s: number[] = Array(k + 1).fill(0); for (let j = 0; j < k; j++) { s[j + 1] = (s[j] + f[i - 1][j]) % mod; } for (let j = 0; j < k; j++) { const l = Math.max(0, j - x); f[i][j] = (s[j + 1] - s[l] + mod) % mod; } } let sum = 0; for (let j = 0; j < k; j++) { sum = (sum + f[m][j]) % mod; } return (ans - sum + mod) % mod; }