Sponsored
Sponsored
This approach uses dynamic programming to build up the solution by storing the number of strings of length n ending with each vowel, based on the rules provided. We use a table where each row corresponds to a length from 1 to n, and each column corresponds to a vowel. The value at each cell (i, j) represents the number of strings of length i that end with the respective vowel j.
We update this table iteratively by considering the transition rules from one vowel to another, ensuring only valid transitions contribute to the count. Finally, we sum up the counts for all vowels at length n to get the result.
Time Complexity: O(n), since we iterate through each position up to n.
Space Complexity: O(1), since we only keep track of the current and next states without additional memory usage.
1public class VowelPermutation {
2 public int countVowelPermutation(int n) {
3 int MOD = 1000000007;
4 long[] dp = new long[]{1, 1, 1, 1, 1}; // a, e, i, o, u
5 for (int i = 1; i < n; i++) {
6 long[] dpNext = new long[5];
7 dpNext[0] = (dp[1] + dp[2] + dp[4]) % MOD; // a follows e, i, u
8 dpNext[1] = (dp[0] + dp[2]) % MOD; // e follows a, i
9 dpNext[2] = (dp[1] + dp[3]) % MOD; // i follows e, o
10 dpNext[3] = dp[2] % MOD; // o follows i
11 dpNext[4] = (dp[2] + dp[3]) % MOD; // u follows i, o
12 dp = dpNext;
13 }
14 long sum = 0;
15 for (long x : dp) sum = (sum + x) % MOD;
16 return (int) sum;
17 }
18
19 public static void main(String[] args) {
20 VowelPermutation vp = new VowelPermutation();
21 System.out.println(vp.countVowelPermutation(1)); // Output: 5
22 System.out.println(vp.countVowelPermutation(2)); // Output: 10
23 }
24}This Java solution maintains a running array of possible vowel endings for strings of increasing length. We use the modulo operation to ensure numbers do not exceed limits and transition according to logical rules for valid strings. Using a single loop iterating from 1 to n-1, it iteratively updates the array with counts for current string lengths based on allowable preceding vowels.
This approach is similar to the previous one but breaks down the state transitions further into distinct functions, or transitions explicitly defined between states (vowels). It effectively uses a dynamic programming table but emphasizes clear rules defining how counts from one step translate to the next.
Time Complexity: O(n) for calculations across string length iteratively.
Space Complexity: O(1), utilizing a constant array scale unrelated to n.
1#include <iostream>
2#include <vector>
3
4class VowelPermutation {
5public:
int countVowelPermutation(int n) {
const int MOD = 1000000007;
std::vector<long> dp(5, 1); // a, e, i, o, u
for (int i = 1; i < n; ++i) {
std::vector<long> dpNext(5);
dpNext[0] = (dp[1] + dp[2] + dp[4]) % MOD; // a follows e, i, u
dpNext[1] = (dp[0] + dp[2]) % MOD; // e follows a, i
dpNext[2] = (dp[1] + dp[3]) % MOD; // i follows e, o
dpNext[3] = dp[2] % MOD; // o follows i
dpNext[4] = (dp[2] + dp[3]) % MOD; // u follows i, o
dp = dpNext;
}
long sum = 0;
for (long x : dp) sum = (sum + x) % MOD;
return sum;
}
};
int main() {
VowelPermutation vp;
std::cout << vp.countVowelPermutation(1) << std::endl; // Output: 5
std::cout << vp.countVowelPermutation(2) << std::endl; // Output: 10
return 0;
}The C++ code offers a slightly more verbose approach, further clarifying transitions between each vowel index state. Functional decomposition is used by specifying transition rules explicitly for each vowel state, showing how dp[i] evolves into dp[next]. This approach emphasizes clarity of state changes across each step n.