101 Logo
onenoughtone

Code Implementation

Count Vowels Permutation Implementation

Below is the implementation of the count vowels permutation:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/**
 * Count the number of strings of length n that can be formed under the given rules.
 * Dynamic Programming (2D) approach.
 *
 * @param {number} n - Length of the strings
 * @return {number} - Number of valid strings
 */
function countVowelPermutation(n) {
  const MOD = 1000000007;
 
  // Initialize DP array
  // dp[i][j] = number of valid strings of length i that end with vowel j
  // j: 0 = 'a', 1 = 'e', 2 = 'i', 3 = 'o', 4 = 'u'
  const dp = Array(n + 1).fill().map(() => Array(5).fill(0));
 
  // Base cases: there is one valid string of length 1 for each vowel
  for (let j = 0; j < 5; j++) {
    dp[1][j] = 1;
  }
 
  // Fill DP array
  for (let i = 2; i <= n; i++) {
    // Strings ending with 'a' (can only be formed by appending 'a' to strings ending with 'e', 'i', or 'u')
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % MOD;
 
    // Strings ending with 'e' (can only be formed by appending 'e' to strings ending with 'a' or 'i')
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
 
    // Strings ending with 'i' (can only be formed by appending 'i' to strings ending with 'e' or 'o')
    dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % MOD;
 
    // Strings ending with 'o' (can only be formed by appending 'o' to strings ending with 'i')
    dp[i][3] = dp[i - 1][2];
 
    // Strings ending with 'u' (can only be formed by appending 'u' to strings ending with 'i' or 'o')
    dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
  }
 
  // Calculate the final answer: sum of dp[n][j] for all j from 0 to 4
  let result = 0;
  for (let j = 0; j < 5; j++) {
    result = (result + dp[n][j]) % MOD;
  }
 
  return result;
}
 
/**
 * Count the number of strings of length n that can be formed under the given rules.
 * Dynamic Programming with Space Optimization.
 *
 * @param {number} n - Length of the strings
 * @return {number} - Number of valid strings
 */
function countVowelPermutationOptimized(n) {
  const MOD = 1000000007;
 
  // Initialize arrays for previous and current lengths
  let prev = Array(5).fill(1);  // Base case: one valid string of length 1 for each vowel
  let curr = Array(5).fill(0);
 
  // Fill arrays
  for (let i = 2; i <= n; i++) {
    // Strings ending with 'a' (can only be formed by appending 'a' to strings ending with 'e', 'i', or 'u')
    curr[0] = (prev[1] + prev[2] + prev[4]) % MOD;
 
    // Strings ending with 'e' (can only be formed by appending 'e' to strings ending with 'a' or 'i')
    curr[1] = (prev[0] + prev[2]) % MOD;
 
    // Strings ending with 'i' (can only be formed by appending 'i' to strings ending with 'e' or 'o')
    curr[2] = (prev[1] + prev[3]) % MOD;
 
    // Strings ending with 'o' (can only be formed by appending 'o' to strings ending with 'i')
    curr[3] = prev[2];
 
    // Strings ending with 'u' (can only be formed by appending 'u' to strings ending with 'i' or 'o')
    curr[4] = (prev[2] + prev[3]) % MOD;
 
    // Update prev array
    prev = [...curr];
  }
 
  // Calculate the final answer: sum of prev[j] for all j from 0 to 4
  return prev.reduce((sum, val) => (sum + val) % MOD, 0);
}
 
/**
 * Count the number of strings of length n that can be formed under the given rules.
 * Matrix Exponentiation approach.
 *
 * @param {number} n - Length of the strings
 * @return {number} - Number of valid strings
 */
function countVowelPermutationMatrix(n) {
  const MOD = 1000000007;
 
  // If n is 1, return 5 (one valid string of length 1 for each vowel)
  if (n === 1) {
    return 5;
  }
 
  // Define the transition matrix
  const matrix = [
    [0, 1, 1, 0, 1],  // a can be followed by e, i, u
    [1, 0, 1, 0, 0],  // e can be followed by a, i
    [0, 1, 0, 1, 0],  // i can be followed by e, o
    [0, 0, 1, 0, 0],  // o can be followed by i
    [0, 0, 1, 1, 0]   // u can be followed by i, o
  ];
 
  // Compute matrix^(n-1)
  const resultMatrix = matrixPower(matrix, n - 1, MOD);
 
  // Calculate the final answer: sum of all elements in the result matrix
  let result = 0;
  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      result = (result + resultMatrix[i][j]) % MOD;
    }
  }
 
  return result;
}
 
/**
 * Compute the power of a matrix using binary exponentiation.
 *
 * @param {number[][]} matrix - The base matrix
 * @param {number} n - The exponent
 * @param {number} mod - The modulo value
 * @return {number[][]} - The resulting matrix
 */
function matrixPower(matrix, n, mod) {
  // Base case: matrix^0 = identity matrix
  if (n === 0) {
    const identity = Array(5).fill().map(() => Array(5).fill(0));
    for (let i = 0; i < 5; i++) {
      identity[i][i] = 1;
    }
    return identity;
  }
 
  // If n is odd, compute matrix^(n-1) * matrix
  if (n % 2 === 1) {
    const result = matrixPower(matrix, n - 1, mod);
    return multiplyMatrices(result, matrix, mod);
  }
 
  // If n is even, compute (matrix^(n/2))^2
  const half = matrixPower(matrix, Math.floor(n / 2), mod);
  return multiplyMatrices(half, half, mod);
}
 
/**
 * Multiply two matrices.
 *
 * @param {number[][]} a - First matrix
 * @param {number[][]} b - Second matrix
 * @param {number} mod - The modulo value
 * @return {number[][]} - The product of the two matrices
 */
function multiplyMatrices(a, b, mod) {
  const result = Array(5).fill().map(() => Array(5).fill(0));
 
  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      for (let k = 0; k < 5; k++) {
        result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod;
      }
    }
  }
 
  return result;
}
 
// Test cases
console.log(countVowelPermutation(1));  // 5
console.log(countVowelPermutation(2));  // 10
console.log(countVowelPermutation(5));  // 68
 
console.log(countVowelPermutationOptimized(1));  // 5
console.log(countVowelPermutationOptimized(2));  // 10
console.log(countVowelPermutationOptimized(5));  // 68
 
console.log(countVowelPermutationMatrix(1));  // 5
console.log(countVowelPermutationMatrix(2));  // 10
console.log(countVowelPermutationMatrix(5));  // 68

Step-by-Step Explanation

Let's break down the implementation:

  1. Define the Problem: Understand the rules for forming valid strings with vowels and the constraints on which vowel can follow another.
  2. Initialize DP Array: Set up a dynamic programming array to keep track of the number of valid strings of each length ending with each vowel.
  3. Establish Base Cases: Define the base case: there is one valid string of length 1 for each vowel.
  4. Fill DP Array: For each length and each vowel, calculate the number of valid strings by considering all possible previous vowels that can lead to the current vowel.
  5. Calculate Final Answer: Sum up the number of valid strings of the target length ending with each vowel, applying the modulo operation to avoid integer overflow.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone