Number of distinct words of size N with at most K contiguous vowels

Last Updated : 11 Oct, 2023

Given two integers N and K, the task is to find the number of distinct strings consisting of lowercase alphabets of length N that can be formed with at-most K contiguous vowels. As the answer may be too large, print answer%1000000007.

Input: N = 1, K = 0
Output: 21
Explanation: All the 21 consonants are there which has 0 contiguous vowels and are of length 1.

Input: N = 1, K = 1
Output: 26

Approach: The idea to solve this problem is based on dynamic programming. Follow the steps below to solve the problem:

Let dp[i][j] be the number of ways to make distinct strings of length i where the last j characters of the string are vowels.
So the states of dynamic programming are:
- If j = 0, then dp[i][j] = (dp[i-1][0] + dp[i-1][1] +……+ dp[i-1][K])*21(represented by the integer variable sum) because the last added character should be a consonant than only the value of j will become 0 irrespective of its value on previous states.
- If i<j then dp[i][j] = 0. Since it is not possible to create a string containing j vowels and has a length less than j.
- If i == j, then dp[i][j] = 5ⁱbecause the number of characters in the string is equal to the number of vowels, therefore all the characters should be vowels.
- If j<i then dp[i][j] = dp[i-1][j-1]*5 because a string of length i with last j characters vowel can be made only if the last character is the vowel and the string of length i-1 has last j – 1 character as vowels.
Print the sum of dp[n][0] + dp[n][1] + …… + dp[n][K] as the answer.

Below is the implementation of the above Approach

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Power function to calculate
// long powers with mod
long long int power(long long int x,
                    long long int y,
                    long long int p)
{
    long long int res = 1ll;
 
    x = x % p;
 
    if (x == 0)
        return 0;
 
    while (y > 0) {
 
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
int kvowelwords(int N, int K)
{
 
    long long int i, j;
    long long int MOD = 1000000007;
 
    // Array dp to store number of ways
    long long int dp[N + 1][K + 1] = { 0 };
 
    long long int sum = 1;
    for (i = 1; i <= N; i++) {
 
        // dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
        dp[i][0] = sum * 21;
        dp[i][0] %= MOD;
 
        // Now setting sum to be dp[i][0]
        sum = dp[i][0];
 
        for (j = 1; j <= K; j++) {
            // If j>i, no ways are possible to create
            // a string with length i and vowel j
            if (j > i)
                dp[i][j] = 0;
            else if (j == i) {
                // If j = i all the character should
                // be vowel
                dp[i][j] = power(5ll, i, MOD);
            }
            else {
                // dp[i][j] relation with dp[i-1][j-1]
                dp[i][j] = dp[i - 1][j - 1] * 5;
            }
 
            dp[i][j] %= MOD;
 
            // Adding dp[i][j] in the sum
            sum += dp[i][j];
            sum %= MOD;
        }
    }
 
    return sum;
}
// Driver Program
int main()
{
    // Input
    int N = 3;
    int K = 3;
 
    // Function Call
    cout << kvowelwords(N, K) << endl;
    return 0;
}

C

// C program for the above approach
#include <stdio.h>
#include <string.h>
 
long long int dp[10000][10000];
 
// Power function to calculate
// long powers with mod
long long int power(long long int x,
                    long long int y,
                    long long int p)
{
    long long int res = 1ll;
 
    x = x % p;
 
    if (x == 0)
        return 0;
 
    while (y > 0) {
 
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
int kvowelwords(int N, int K)
{
 
    long long int i, j;
    long long int MOD = 1000000007;
     
   
    long long int sum = 1;
    for (i = 1; i <= N; i++) {
 
        // dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
        dp[i][0] = sum * 21;
        dp[i][0] %= MOD;
 
        // Now setting sum to be dp[i][0]
        sum = dp[i][0];
 
        for (j = 1; j <= K; j++) {
            // If j>i, no ways are possible to create
            // a string with length i and vowel j
            if (j > i)
                dp[i][j] = 0;
            else if (j == i) {
                // If j = i all the character should
                // be vowel
                dp[i][j] = power(5ll, i, MOD);
            }
            else {
                // dp[i][j] relation with dp[i-1][j-1]
                dp[i][j] = dp[i - 1][j - 1] * 5;
            }
 
            dp[i][j] %= MOD;
 
            // Adding dp[i][j] in the sum
            sum += dp[i][j];
            sum %= MOD;
        }
    }
 
    return sum;
}
// Driver Program
int main()
{
    // Input
    int N = 3;
    int K = 3;
     
    memset(dp,0,N*K*sizeof (long long int));
 
    // Function Call
    printf("%d",kvowelwords(N, K));
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Power function to calculate
// long powers with mod
static int power(int x, int y, int p)
{
    int res = 1;
    x = x % p;
  
    if (x == 0)
        return 0;
  
    while (y > 0)
    {
        if ((y & 1) != 0)
            res = (res * x) % p;
             
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
  
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
static int kvowelwords(int N, int K)
{
    int i, j;
    int MOD = 1000000007;
  
    // Array dp to store number of ways
    int[][] dp = new int[N + 1][K + 1] ;
  
    int sum = 1;
    for(i = 1; i <= N; i++)
    {
         
        // dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
        dp[i][0] = sum * 21;
        dp[i][0] %= MOD;
  
        // Now setting sum to be dp[i][0]
        sum = dp[i][0];
  
        for(j = 1; j <= K; j++)
        {
             
            // If j>i, no ways are possible to create
            // a string with length i and vowel j
            if (j > i)
                dp[i][j] = 0;
                 
            else if (j == i) 
            {
                 
                // If j = i all the character should
                // be vowel
                dp[i][j] = power(5, i, MOD);
            }
            else
            {
                 
                // dp[i][j] relation with dp[i-1][j-1]
                dp[i][j] = dp[i - 1][j - 1] * 5;
            }
  
            dp[i][j] %= MOD;
  
            // Adding dp[i][j] in the sum
            sum += dp[i][j];
            sum %= MOD;
        }
    }
    return sum;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input
    int N = 3;
    int K = 3;
  
    // Function Call
    System.out.println( kvowelwords(N, K));
}
}
 
// This code is contributed by target_2

Python3

# Python3 program for the above approach
 
# Power function to calculate
# long powers with mod
def power(x, y, p):
     
    res = 1
    x = x % p
 
    if (x == 0):
        return 0
 
    while (y > 0):
        if (y & 1):
            res = (res * x) % p
             
        y = y >> 1
        x = (x * x) % p
         
    return res
 
# Function for finding number of ways to
# create string with length N and atmost
# K contiguous vowels
def kvowelwords(N, K):
 
    i, j = 0, 0
    MOD = 1000000007
 
    # Array dp to store number of ways
    dp = [[0 for i in range(K + 1)] 
             for i in range(N + 1)]
 
    sum = 1
    for i in range(1, N + 1):
         
        #dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
        dp[i][0] = sum * 21
        dp[i][0] %= MOD
 
        # Now setting sum to be dp[i][0]
        sum = dp[i][0]
 
        for j in range(1, K + 1):
             
            # If j>i, no ways are possible to create
            # a string with length i and vowel j
            if (j > i):
                dp[i][j] = 0
            elif (j == i):
                 
                # If j = i all the character should
                # be vowel
                dp[i][j] = power(5, i, MOD)
            else:
                 
                # dp[i][j] relation with dp[i-1][j-1]
                dp[i][j] = dp[i - 1][j - 1] * 5
 
            dp[i][j] %= MOD
 
            # Adding dp[i][j] in the sum
            sum += dp[i][j]
            sum %= MOD
 
    return sum
     
# Driver Code
if __name__ == '__main__':
     
    # Input
    N = 3
    K = 3
 
    # Function Call
    print (kvowelwords(N, K))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Power function to calculate
// long powers with mod
static int power(int x, int y, int p)
{
    int res = 1;
    x = x % p;
  
    if (x == 0)
        return 0;
  
    while (y > 0)
    {
        if ((y & 1) != 0)
            res = (res * x) % p;
             
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
  
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
static int kvowelwords(int N, int K)
{
    int i, j;
    int MOD = 1000000007;
  
    // Array dp to store number of ways
    int[,] dp = new int[N + 1, K + 1];
  
    int sum = 1;
    for(i = 1; i <= N; i++)
    {
         
        // dp[i][0] = (dp[i-1, 0]+dp[i-1, 1]..dp[i-1][k])*21
        dp[i, 0] = sum * 21;
        dp[i, 0] %= MOD;
  
        // Now setting sum to be dp[i][0]
        sum = dp[i, 0];
  
        for(j = 1; j <= K; j++)
        {
             
            // If j>i, no ways are possible to create
            // a string with length i and vowel j
            if (j > i)
                dp[i, j] = 0;
                 
            else if (j == i) 
            {
                 
                // If j = i all the character should
                // be vowel
                dp[i, j] = power(5, i, MOD);
            }
            else
            {
                 
                // dp[i][j] relation with dp[i-1][j-1]
                dp[i, j] = dp[i - 1, j - 1] * 5;
            }
  
            dp[i, j] %= MOD;
  
            // Adding dp[i][j] in the sum
            sum += dp[i, j];
            sum %= MOD;
        }
    }
    return sum;
}
 
// Driver Code
public static void Main()
{
     
    // Input
    int N = 3;
    int K = 3;
  
    // Function Call
    Console.Write(kvowelwords(N, K));
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
 
// JavaScript code for above approach
 
// Power function to calculate
// long powers with mod
function power(x, y, p)
{
    let res = 1;
    x = x % p;
  
    if (x == 0)
        return 0;
  
    while (y > 0)
    {
        if ((y & 1) != 0)
            res = (res * x) % p;
             
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
  
// Function for finding number of ways to
// create string with length N and atmost
// K contiguous vowels
function kvowelwords(N, K)
{
    let i, j;
    let MOD = 1000000007;
  
    // Array dp to store number of ways
    let dp = new Array(N + 1)
    // Loop to create 2D array using 1D array
    for (i = 0; i < dp.length; i++) {
        dp[i] = new Array(K + 1);
    }
  
    let sum = 1;
    for(i = 1; i <= N; i++)
    {
         
        // dp[i][0] = (dp[i-1][0]+dp[i-1][1]..dp[i-1][k])*21
        dp[i][0] = sum * 21;
        dp[i][0] %= MOD;
  
        // Now setting sum to be dp[i][0]
        sum = dp[i][0];
  
        for(j = 1; j <= K; j++)
        {
             
            // If j>i, no ways are possible to create
            // a string with length i and vowel j
            if (j > i)
                dp[i][j] = 0;
                 
            else if (j == i) 
            {
                 
                // If j = i all the character should
                // be vowel
                dp[i][j] = power(5, i, MOD);
            }
            else
            {
                 
                // dp[i][j] relation with dp[i-1][j-1]
                dp[i][j] = dp[i - 1][j - 1] * 5;
            }
  
            dp[i][j] %= MOD;
  
            // Adding dp[i][j] in the sum
            sum += dp[i][j];
            sum %= MOD;
        }
    }
    return sum;
}
 
// Driver Code
 
    // Input
    let N = 3;
    let K = 3;
  
    // Function Call
    document.write( kvowelwords(N, K));
     
    // This code is contributed by sanjoy_62.
</script>

Output

Time Complexity: O(N×K)
Auxiliary Space: O(N×K)

Approach 2: Recursion with Memoization

C++

#include <iostream>
#include <vector>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int N, K;
vector<vector<vector<int>>> memo;
 
int countWays(int pos, int vowels, bool prevVowel) {
    if (pos == N) return 1;
    if (memo[pos][vowels][prevVowel] != -1) return memo[pos][vowels][prevVowel];
 
    int res = 0;
    // Add a consonant
    res = (res + 21 * countWays(pos + 1, 0, false)) % MOD;
    // Add a vowel
    if (prevVowel && vowels == K) {
        res = (res + 0) % MOD;
    } else {
        res = (res + 5 * countWays(pos + 1, prevVowel ? vowels + 1 : 1, true)) % MOD;
    }
 
    return memo[pos][vowels][prevVowel] = res;
}
 
int kvowelwords(int n, int k) {
    N = n; K = k;
    memo.assign(N, vector<vector<int>>(K + 1, vector<int>(2, -1)));
    return countWays(0, 0, false);
}
 
int main() {
    cout << kvowelwords(3, 3) << endl;
    return 0;
}

Java

import java.util.Arrays;
 
public class KVowelWords {
    static final int MOD = 1000000007;
    static int N, K;
    static int[][][] memo;
 
    // Function to count the number of k-vowel words
    static int countWays(int pos, int vowels, boolean prevVowel) {
        if (pos == N) return 1;
        if (memo[pos][vowels][prevVowel ? 1 : 0] != -1) return memo[pos][vowels][prevVowel ? 1 : 0];
 
        int res = 0;
        // Add a consonant
        res = (res + 21 * countWays(pos + 1, 0, false)) % MOD;
        // Add a vowel
        if (prevVowel && vowels == K) {
            res = (res + 0) % MOD;
        } else {
            res = (res + 5 * countWays(pos + 1, prevVowel ? vowels + 1 : 1, true)) % MOD;
        }
 
        return memo[pos][vowels][prevVowel ? 1 : 0] = res;
    }
 
    // Function to compute the number of k-vowel words
    static int kvowelwords(int n, int k) {
        N = n; K = k;
        memo = new int[N][K + 1][2];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= K; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        return countWays(0, 0, false);
    }
 
    public static void main(String[] args) {
        System.out.println(kvowelwords(3, 3));
    }
}

Python3

MOD = 10**9 + 7
 
def countWays(pos, vowels, prevVowel, N, K, memo):
    if pos == N:
        return 1
 
    if memo[pos][vowels][prevVowel] != -1:
        return memo[pos][vowels][prevVowel]
 
    res = 0
    # Add a consonant
    res = (res + 21 * countWays(pos + 1, 0, False, N, K, memo)) % MOD
    # Add a vowel
    if prevVowel and vowels == K:
        res = (res + 0) % MOD
    else:
        res = (res + 5 * countWays(pos + 1, vowels + 1 if prevVowel else 1, True, N, K, memo)) % MOD
 
    memo[pos][vowels][prevVowel] = res
    return res
 
def kvowelwords(n, k):
    N = n
    K = k
    memo = [[[-1 for _ in range(2)] for _ in range(K + 1)] for _ in range(N)]
    return countWays(0, 0, False, N, K, memo)
 
if __name__ == "__main__":
    print(kvowelwords(3, 3))

C#

using System;
using System.Collections.Generic;
 
class Program
{
    const int MOD = 1000000007;
 
    static int N, K;
    static List<List<List<int>>> memo;
 
    static int CountWays(int pos, int vowels, bool prevVowel)
    {
        if (pos == N) return 1;
        if (memo[pos][vowels][prevVowel ? 1 : 0] != -1) return memo[pos][vowels][prevVowel ? 1 : 0];
 
        int res = 0;
        // Add a consonant
        res = (res + 21 * CountWays(pos + 1, 0, false)) % MOD;
        // Add a vowel
        if (prevVowel && vowels == K)
        {
            res = (res + 0) % MOD;
        }
        else
        {
            res = (res + 5 * CountWays(pos + 1, prevVowel ? vowels + 1 : 1, true)) % MOD;
        }
 
        return memo[pos][vowels][prevVowel ? 1 : 0] = res;
    }
 
    static int Kvowelwords(int n, int k)
    {
        N = n; K = k;
        memo = new List<List<List<int>>>(N);
        for (int i = 0; i < N; i++)
        {
            memo.Add(new List<List<int>>(K + 1));
            for (int j = 0; j <= K; j++)
            {
                memo[i].Add(new List<int> { -1, -1 });
            }
        }
        return CountWays(0, 0, false);
    }
 
    static void Main(string[] args)
    {
        Console.WriteLine(Kvowelwords(3, 3));
    }
}

Javascript

const MOD = 1000000007;
 
let N, K;
let memo;
 
// Function to count the ways to form words with specific vowel and consonant rules
function countWays(pos, vowels, prevVowel) {
    // Base case: If we've processed all positions in the word
    if (pos === N) return 1;
 
    // If we have already computed this state, return it from memoization
    if (memo[pos][vowels][prevVowel ? 1 : 0] !== -1) {
        return memo[pos][vowels][prevVowel ? 1 : 0];
    }
 
    let res = 0;
 
    // Add a consonant: There are 21 consonants available
    res = (res + 21 * countWays(pos + 1, 0, false)) % MOD;
 
    // Add a vowel
    if (prevVowel && vowels === K) {
        // If the previous character was a vowel and we've already used K vowels, we can't add more
        res = (res + 0) % MOD;
    } else {
        // Add a vowel: There are 5 vowels available
        res = (res + 5 * countWays(pos + 1, prevVowel ? vowels + 1 : 1, true)) % MOD;
    }
 
    // Memoize the result and return it
    memo[pos][vowels][prevVowel ? 1 : 0] = res;
    return res;
}
 
// Function to calculate the count of words based on given parameters
function kvowelWords(n, k) {
    N = n; // Total word length
    K = k; // Maximum allowed vowels
 
    // Initialize memoization table
    memo = new Array(N).fill(null).map(() => {
        return new Array(K + 1).fill(null).map(() => {
            return [-1, -1];
        });
    });
 
    // Start the recursive counting
    return countWays(0, 0, false);
}
 
// Example usage:
console.log(kvowelWords(3, 3)); // Output the count of words following the rules

Output

Time Complexity: O(N * K)
Auxiliary Space: O(N * K)

Suggest improvement

Alternate vowel and consonant string

Merge two unsorted linked lists to get a sorted list - Set 2

Share your thoughts in the comments

Number of distinct words of size N with at most K contiguous vowels

C++

C

Java

Python3

C#

Javascript

Approach 2: Recursion with Memoization

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?