Count String Permutations | HackerRank Certification

Count all possible N-length vowel permutations that can be generated based on the given conditions

Given an integer N, the task is to count the number of N-length strings consisting of lowercase vowels that can be generated based the following conditions:

• Each ‘a’ may only be followed by an ‘e’.
• Each ‘e’ may only be followed by an ‘a’ or an ‘i’.
• Each ‘i’ may not be followed by another ‘i’.
• Each ‘o’ may only be followed by an ‘i’ or a ‘u’.
• Each ‘u’ may only be followed by an ‘a’.a

nput: N = 1
Output: 5
Explanation: All strings that can be formed are: “a”, “e”, “i”, “o” and “u”.

Input: N = 2
Output: 10
Explanation: All strings that can be formed are: “ae”, “ea”, “ei”, “ia”, “ie”, “io”, “iu”, “oi”, “ou” and “ua”.

using System;

using System.Collections.Generic;

class StringPermutation {

   

    static int countVowelPermutation(int n)

    {

   

        int MOD = (int)(1e9 + 7);

        long[,] dp = new long[n + 1, 5];

        for (int i = 0; i < 5; i++) {

            dp[1, i] = 1;

        }

        List<List<int>> relation = new List<List<int>>();

        relation.Add(new List<int> { 1 });

        relation.Add(new List<int> { 0, 2 });

        relation.Add(new List<int> { 0, 1, 3, 4 });

        relation.Add(new List<int> { 2, 4 });

        relation.Add(new List<int> { 0 });

        for (int i = 1; i < n; i++)

        {

            for (int u = 0; u < 5; u++)

            {

                dp[i + 1, u] = 0;

                foreach(int v in relation[u])

                {

                    dp[i + 1, u] += dp[i, v] % MOD;

                }

            }

        }

        long ans = 0;

        for (int i = 0; i < 5; i++)

        {

            ans = (ans + dp[n, i]) % MOD;

        }

        return (int)ans;

    }

    static void Main() {

        int N = 2;

        Console.WriteLine(countVowelPermutation(N));

    }

}