Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each equal-character run of length r could originate from any positive length from one through r. These choices are independent, giving the product of run lengths before the minimum-length restriction. Subtract the combinations whose total original length is below k.

Approach

Extract the run lengths and compute their product modulo 1,000,000,007. If there are already at least k runs, every possible original has sufficient length, so return that product.

Otherwise let dp[i][j] count choices from the first i runs producing exactly j characters, storing only lengths below k. Start with dp[0][0] = 1. For a run of length r, the previous length can range from max(0, j - r) through j - 1. Build prefix sums of the previous row to evaluate this interval in constant table operations.

Subtract the sum of the last row from the unrestricted product and normalize modulo the modulus. The supplied implementations retain exact counts inside this DP, rather than reducing every state, so their large-integer cost matters in the complexity analysis.

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(word)

        groups = []
        res = 1
        cnt = 1

        for i in range(1, n):
            if word[i] == word[i - 1]:
                cnt += 1
            else:
                groups.append(cnt)
                res = (res * cnt) % MOD
                cnt = 1

        groups.append(cnt)
        res = (res * cnt) % MOD

        if k <= len(groups):
            return res

        # k > len(groups): dp
        dp = [[0] * k for _ in range(len(groups) + 1)]
        dp[0][0] = 1

        for i in range(1, len(groups) + 1):
            pref = [0] * k
            pref[0] = dp[i - 1][0]

            for idx in range(1, k):
                pref[idx] = pref[idx - 1] + dp[i - 1][idx]

            for j in range(1, k):
                left = j - 1 - groups[i - 1]
                pre_s = pref[j - 1]
                if left >= 0:
                    pre_s -= pref[left]
                dp[i][j] = pre_s

        return (res - sum(dp[-1])) % MOD

Complexity analysis

Let n = word.length and g be the number of equal-character runs. If g >= k, both versions take O(n) time and O(g) auxiliary machine words for the run lengths. Otherwise, let B >= 1 be the largest bit length of an exact DP count, prefix sum or final too-short total. B = O(k), since these count positive compositions with total length below k. Time is O(n + gkB), treating the bounded input counters and modular-product arithmetic as constant-size. The full table retains O(gk) entries with up to B bits each; auxiliary storage is O(gkB) bits for integer payloads, plus O(gk + g) machine words for table containers and run lengths. The O(k*B) prefix workspace is included. Counts inside the DP are not reduced modulo the modulus.