Problem

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 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: word = "aabbccdd", k = 7

Output: 5

Explanation:

The possible strings are: `"aabbccdd"`, `"aabbccd"`, `"aabbcdd"`, `"aabccdd"`,
and `"abbccdd"`.

Example 2

1
2
3
4
5
6
7
8


Input: word = "aabbccdd", k = 8

Output: 1

Explanation:

The only possible string is `"aabbccdd"`.

Example 3

1
2
3
4


Input: word = "aaabbb", k = 3

Output: 8

Constraints

  • 1 <= word.length <= 5 * 10^5
  • word consists only of lowercase English letters.
  • 1 <= k <= 2000

Solution

Method 1 – Dynamic Programming with Grouping

Intuition

We can group consecutive identical characters in word and, for each group, decide how many characters to keep (at least 1, up to the group length). The total length of the original string must be at least k. We use dynamic programming to count the number of ways to select how many characters to keep from each group so that the total length is at least k.

Approach

  1. Group the string into consecutive runs of the same character, storing their lengths.
  2. Let dp[i][l] be the number of ways to process the first i groups to get a string of length l.
  3. Initialize dp[0][0] = 1 (no groups, length 0).
  4. For each group, for each possible current length, try all possible numbers of characters to keep from the group (from 1 to group length), and update the DP.
  5. The answer is the sum of all dp[n][l] for l >= k.
  6. Return the answer modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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)
        dp = [0] * (n + 1)
        dp[0] = 1
        for g in groups:
            ndp = [0] * (n + 1)
            for l in range(n + 1):
                if dp[l]:
                    for take in range(1, g + 1):
                        if l + take <= n:
                            ndp[l + take] = (ndp[l + take] + dp[l]) % MOD
            dp = ndp
        return sum(dp[k:]) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    int possibleStringCount(string word, int k) {
        const int MOD = 1e9 + 7;
        int n = word.size();
        vector<int> groups;
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && word[j] == word[i]) ++j;
            groups.push_back(j - i);
            i = j;
        }
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int g : groups) {
            vector<int> ndp(n + 1);
            for (int l = 0; l <= n; ++l) {
                if (dp[l]) {
                    for (int take = 1; take <= g; ++take) {
                        if (l + take <= n)
                            ndp[l + take] = (ndp[l + take] + dp[l]) % MOD;
                    }
                }
            }
            dp = ndp;
        }
        int ans = 0;
        for (int l = k; l <= n; ++l) ans = (ans + dp[l]) % MOD;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func possibleStringCount(word string, k int) int {
    mod := int(1e9 + 7)
    n := len(word)
    groups := []int{}
    for i := 0; i < n; {
        j := i
        for j < n && word[j] == word[i] { j++ }
        groups = append(groups, j-i)
        i = j
    }
    dp := make([]int, n+1)
    dp[0] = 1
    for _, g := range groups {
        ndp := make([]int, n+1)
        for l := 0; l <= n; l++ {
            if dp[l] > 0 {
                for take := 1; take <= g; take++ {
                    if l+take <= n {
                        ndp[l+take] = (ndp[l+take] + dp[l]) % mod
                    }
                }
            }
        }
        dp = ndp
    }
    ans := 0
    for l := k; l <= n; l++ {
        ans = (ans + dp[l]) % mod
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public int possibleStringCount(String word, int k) {
        int MOD = 1_000_000_007;
        int n = word.length();
        List<Integer> groups = new ArrayList<>();
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && word.charAt(j) == word.charAt(i)) ++j;
            groups.add(j - i);
            i = j;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int g : groups) {
            int[] ndp = new int[n + 1];
            for (int l = 0; l <= n; ++l) {
                if (dp[l] > 0) {
                    for (int take = 1; take <= g; ++take) {
                        if (l + take <= n)
                            ndp[l + take] = (ndp[l + take] + dp[l]) % MOD;
                    }
                }
            }
            dp = ndp;
        }
        int ans = 0;
        for (int l = k; l <= n; ++l) ans = (ans + dp[l]) % MOD;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    fun possibleStringCount(word: String, k: Int): Int {
        val MOD = 1_000_000_007
        val n = word.length
        val groups = mutableListOf<Int>()
        var i = 0
        while (i < n) {
            var j = i
            while (j < n && word[j] == word[i]) j++
            groups.add(j - i)
            i = j
        }
        var dp = IntArray(n + 1)
        dp[0] = 1
        for (g in groups) {
            val ndp = IntArray(n + 1)
            for (l in 0..n) {
                if (dp[l] > 0) {
                    for (take in 1..g) {
                        if (l + take <= n)
                            ndp[l + take] = (ndp[l + take] + dp[l]) % MOD
                    }
                }
            }
            dp = ndp
        }
        var ans = 0
        for (l in k..n) ans = (ans + dp[l]) % MOD
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

impl Solution {
    pub fn possible_string_count(word: String, k: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = word.len();
        let bytes = word.as_bytes();
        let mut groups = vec![];
        let mut i = 0;
        while i < n {
            let mut j = i;
            while j < n && bytes[j] == bytes[i] { j += 1; }
            groups.push(j - i);
            i = j;
        }
        let mut dp = vec![0; n + 1];
        dp[0] = 1;
        for &g in &groups {
            let mut ndp = vec![0; n + 1];
            for l in 0..=n {
                if dp[l] > 0 {
                    for take in 1..=g {
                        if l + take <= n {
                            ndp[l + take] = (ndp[l + take] + dp[l]) % MOD;
                        }
                    }
                }
            }
            dp = ndp;
        }
        let mut ans = 0;
        for l in k as usize..=n {
            ans = (ans + dp[l]) % MOD;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    possibleStringCount(word: string, k: number): number {
        const MOD = 1e9 + 7;
        const n = word.length;
        const groups: number[] = [];
        let i = 0;
        while (i < n) {
            let j = i;
            while (j < n && word[j] === word[i]) j++;
            groups.push(j - i);
            i = j;
        }
        let dp = new Array(n + 1).fill(0);
        dp[0] = 1;
        for (const g of groups) {
            const ndp = new Array(n + 1).fill(0);
            for (let l = 0; l <= n; ++l) {
                if (dp[l]) {
                    for (let take = 1; take <= g; ++take) {
                        if (l + take <= n) {
                            ndp[l + take] = (ndp[l + take] + dp[l]) % MOD;
                        }
                    }
                }
            }
            dp = ndp;
        }
        let ans = 0;
        for (let l = k; l <= n; ++l) ans = (ans + dp[l]) % MOD;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — For each group, we may try up to n lengths, and for each, up to n group sizes.
  • 🧺 Space complexity: O(n) — For the DP array.