Sponsored
Sponsored
We can use dynamic programming to solve this problem whereby we maintain a table dp[i][j] where i is the length of the string and j is the vowel index from the sorted vowels list [0: 'a', 1: 'e', 2: 'i', 3: 'o', 4: 'u']. Each cell dp[i][j] represents the number of valid strings of length i using the vowels from index j to the end. We initialize the base case for strings of length 1 and fill the table iteratively.
Time Complexity: O(n * 5 * 5) = O(n), as we have nested loops running across vowels and length.
Space Complexity: O(n * 5), for storing the table.
1#include <stdio.h>
2
3int countVowelStrings(int n) {
4 int dp[n+1][5];
5 for (int j = 0; j < 5; j++) {
6 dp[1][j] = 5 - j;
7 }
8 for (int i = 2; i <= n; i++) {
9 for (int j = 4; j >= 0; j--) {
10 dp[i][j] = 0;
11 for (int k = j; k < 5; k++) {
12 dp[i][j] += dp[i-1][k];
13 }
14 }
15 }
16 return dp[n][0];
17}The algorithm initializes a table where dp[i][j] stores numbers of strings of length i from vowel j onward. It calculates each table entry by summing up the possibilities of extending strings of length i-1 with each vowel.
Instead of counting strings iteratively, we can view the problem as a mathematical combination problem. Since the string is lexicographically sorted, the placement of 'n' vowels among 'a', 'e', 'i', 'o', 'u' is equivalent to distributing 'n' identical items into 5 distinct groups (vowel buckets). We use the combinatorial formula: C(n + m - 1, m - 1) where 'm' is the number of distinct vowels.
Time Complexity: O(n), due to the recursive calculation of combination.
Space Complexity: O(n), for the recursive call stack.
1This JavaScript solution uses a loop to calculate combinations iteratively through the repeated multiplication and division as expressed in combination logic.