kmax-cont-vowels.md

Number of distict Words with k maximum contiguous vowels

Find the number of unique words consisting of lowercase alphabets only of length N that can be formed with at-most K contiguous vowels.

Hint

Sample Input

384 71

Sample Output

233867288

Solution

class Solution {
  public:
    int kvowelwords(int N, int K) {
        
        long long int mod = 1000000007;

        vector<vector<int>> dp(N, vector<int>(K + 1, 0));
        dp[0][0] = 21;
        long long int sum = 21;

        if(K > 0) {
            dp[0][1] = 5;
            sum += 5;
        };

        for(int n = 1; n < N; ++n) {
            sum = dp[n][0] = (sum * 21ll) % mod;
            for(int k = 1; k <= K; ++k) {
                sum += dp[n][k] = (dp[n - 1][k - 1]*5ll) % mod;
                sum %= mod;
            }
        }

        return sum;
    }
};

Accepted