Find the Original Typed String II | Leetcode 3333

class Solution {
    int MOD = 1e9+7;
public:
    int possibleStringCount(string word, int k) {
        //STEP-1: Make runs array
        int n = word.size();
        vector<int> runs(1,1);
        for(int i=1;i<n;++i){
            if(word[i]==word[i-1])  runs.back()++;
            else                    runs.push_back(1);
        }
        //Step-2: Count total combinations
        int total_combinations = 1;
        for(int freq: runs)
            total_combinations = (1LL * total_combinations * freq) % MOD;
        
        if(runs.size()>=k)
            return total_combinations;

        /*
            count[i]=x for 3rd run means: 'x' number of strings can be formed of length 'i',
                                        using the first 3 runs.
        */
        vector<int> count(k), newCount(k), prefix_sum(k);
        count[0] = 1;//1 way to form an empty string by not including any character

        //STEP-3: Count number of strings of different sizes formed by including all runs
        for(int freq: runs){
            //Update Prefix_sum array
            prefix_sum[0] = count[0];
            for(int i=1;i<k;++i)
                prefix_sum[i] = (prefix_sum[i-1] + count[i]) % MOD;
            
            //Make a new run
            for(int i=1;i<k;++i){
                int right = prefix_sum[i-1];
                int left = 0;
                if(i-1-freq >= 0)
                    left = prefix_sum[i-1-freq];
                newCount[i] = (right - left + MOD) % MOD;
            }
            swap(count,newCount);
            fill(newCount.begin(),newCount.end(),0);
        }
        int invalid_combinations = 0;
        for(int i=0;i<k;++i)
            invalid_combinations = (invalid_combinations + count[i]) % MOD;

        return (total_combinations - invalid_combinations + MOD) % MOD;
    }
};
/*
//JAVA
import java.util.ArrayList;
import java.util.List;

class Solution {
    private static final int MOD = (int)1e9 + 7;

    public int possibleStringCount(String word, int k) {
        // STEP-1: Make runs array
        int n = word.length();
        List<Integer> runs = new ArrayList<>();
        runs.add(1);
        for (int i = 1; i < n; ++i) {
            if (word.charAt(i) == word.charAt(i - 1)) {
                runs.set(runs.size() - 1, runs.get(runs.size() - 1) + 1);
            } else {
                runs.add(1);
            }
        }
        
        // Step-2: Count total combinations
        int totalCombinations = 1;
        for (int freq : runs) {
            totalCombinations = (int)((long)totalCombinations * freq % MOD);
        }
        
        if (runs.size() >= k) {
            return totalCombinations;
        }
        
        // STEP-3: Count number of strings of different sizes formed by including all runs
        int[] count = new int[k];
        int[] newCount = new int[k];
        int[] prefixSum = new int[k];
        count[0] = 1; // 1 way to form an empty string by not including any character
        
        for (int freq : runs) {
            // Update PrefixSum array
            prefixSum[0] = count[0];
            for (int i = 1; i < k; ++i) {
                prefixSum[i] = (prefixSum[i - 1] + count[i]) % MOD;
            }
            
            // Make a new run
            for (int i = 1; i < k; ++i) {
                int right = prefixSum[i - 1];
                int left = 0;
                if (i - 1 - freq >= 0) {
                    left = prefixSum[i - 1 - freq];
                }
                newCount[i] = (right - left + MOD) % MOD;
            }
            
            // Swap count and newCount
            int[] temp = count;
            count = newCount;
            newCount = temp;
            // Reset newCount to 0
            Arrays.fill(newCount, 0);
        }
        
        int invalidCombinations = 0;
        for (int i = 0; i < k; ++i) {
            invalidCombinations = (invalidCombinations + count[i]) % MOD;
        }
        
        return (totalCombinations - invalidCombinations + MOD) % MOD;
    }
}

#Python
MOD = 10**9 + 7

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int:
        # STEP-1: Make runs array
        n = len(word)
        runs = [1]
        for i in range(1, n):
            if word[i] == word[i-1]:
                runs[-1] += 1
            else:
                runs.append(1)
        
        # Step-2: Count total combinations
        total_combinations = 1
        for freq in runs:
            total_combinations = (total_combinations * freq) % MOD
        
        if len(runs) >= k:
            return total_combinations
        
        # STEP-3: Count number of strings of different sizes formed by including all runs
        count = [0] * k
        new_count = [0] * k
        prefix_sum = [0] * k
        count[0] = 1  # 1 way to form an empty string by not including any character
        
        for freq in runs:
            # Update prefix_sum array
            prefix_sum[0] = count[0]
            for i in range(1, k):
                prefix_sum[i] = (prefix_sum[i-1] + count[i]) % MOD
            
            # Make a new run
            for i in range(1, k):
                right = prefix_sum[i-1]
                left = 0
                if i - 1 - freq >= 0:
                    left = prefix_sum[i - 1 - freq]
                new_count[i] = (right - left + MOD) % MOD
            
            # Swap count and new_count
            count, new_count = new_count, count
            # Reset new_count to 0
            new_count = [0] * k
        
        invalid_combinations = 0
        for i in range(k):
            invalid_combinations = (invalid_combinations + count[i]) % MOD
        
        return (total_combinations - invalid_combinations + MOD) % MOD
*/