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.
1public int countVowelStrings(int n) {
2 int[][] dp = new int[n + 1][5];
3 for (int j = 0; j < 5; j++) {
4 dp[1][j] = 5 - j;
5 }
6 for (int i = 2; i <= n; i++) {
7 for (int j = 4; j >= 0; j--) {
8 dp[i][j] = 0;
9 for (int k = j; k < 5; k++) {
10 dp[i][j] += dp[i - 1][k];
11 }
12 }
13 }
14 return dp[n][0];
15}In Java, the solution mirrors the same logic using a 2D array where each index reflects the length and starting vowel with nested loops iterating over possible combinations.
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.
This solution provides a direct combinatory calculation using the formula for combinations. The helper function computes combinations recursively.