# Solution For Count Sorted Vowel Strings

Problem Statement:

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Solution:

The problem can be solved using dynamic programming. Let’s define dp[i][j] as the number of strings of length i that end with the j-th vowel (a, e, i, o, u). We can calculate dp[i][j] by summing dp[i-1][k] for k <= j. This is because if we have a string of length i-1 that ends with some vowel k, we can append the vowel j to it and get a string of length i that ends with vowel j. We can compute this for all i and j, with dp[j]=1 for all j.

Finally, we can get the answer by summing dp[n][j] for all j.

Here’s the code:

`class Solution { public: int countVowelStrings(int n) { vector<vector<int>> dp(n+1, vector<int>(5,0)); for(int j=0; j<5; j++) { dp[j] = 1; } for(int i=2; i<=n; i++) { for(int j=0; j<5; j++) { for(int k=0; k<=j; k++) { dp[i][j] += dp[i-1][k]; } } } int ans = 0; for(int j=0; j<5; j++) { ans += dp[n][j]; } return ans; } };`

Time Complexity:

The time complexity of the algorithm is O(n^2) because we have three nested loops, each of size n.

Space Complexity:

The space complexity of the algorithm is O(n^2) because we need to store dp[i][j] for all i and j.

## Step by Step Implementation For Count Sorted Vowel Strings

```public int countVowelStrings(int n) {
// base case
if (n == 1) {
return 5;
}
// a e i o u
// dp[i][j] represents the number of strings of length i that end in the jth vowel
int[][] dp = new int[n + 1];
// there is only one string of length 1
for (int j = 0; j < 5; j++) {
dp[j] = 1;
}
// fill in the rest of the DP array
for (int i = 2; i <= n; i++) {
// the number of strings of length i that end in the jth vowel
// is the sum of the number of strings of length i - 1 that end in all the vowels before the jth vowel
for (int j = 0; j < 5; j++) {
for (int k = 0; k <= j; k++) {
dp[i][j] += dp[i - 1][k];
}
}
}
// the total number of strings is the sum of the number of strings of length n that end in each vowel
int ans = 0;
for (int j = 0; j < 5; j++) {
ans += dp[n][j];
}
return ans;
}```
```def countVowelStrings(self, n: int) -> int:

# a list of all possible vowels
vowels = ['a', 'e', 'i', 'o', 'u']

# a list to store all possible strings
# that can be generated
strings = []

# generate all possible strings
# using backtracking
def backtrack(curr, index):

# if we have generated a string
# of length 'n'
if (len(curr) == n):
strings.append(curr)
return

# iterate over all possible vowels
for i in range(index, len(vowels)):

# append the current vowel to the
# string being generated
backtrack(curr + vowels[i], i)

# call the backtracking function
# with an empty string and index 0
backtrack("", 0)

# return the total number of strings
# that can be generated
return len(strings)```
```var countVowelStrings = function(n) {
// create a set to store all the possible vowel strings
let set = new Set();

// create an array of all the possible vowels
let vowels = ["a", "e", "i", "o", "u"];

// create a recursive helper function that will generate all the possible vowel strings
function generate(curr, n) {
// if we have generated a string with the correct number of characters, add it to the set
if (curr.length === n) {
} else {
// otherwise, loop through all the possible vowels and add each one to the current string
for (let i = 0; i < vowels.length; i++) {
generate(curr + vowels[i], n);
}
}
}

// call the recursive helper function to generate all the possible strings
generate("", n);

// return the size of the set (which is the number of unique strings)
return set.size;
};```
```int countVowelStrings(int n) {

// Base case
if (n == 1)
return 5;

// Recursive case
// 'a' is considered as vowel in this question
int ans = countVowelStrings(n - 1);

// e is considered as vowel
for (int i = n - 2; i >= 0; i--)
ans += countVowelStrings(i);

// u is considered as vowel
for (int i = n - 3; i >= 0; i--)
ans += countVowelStrings(i);

return ans;
}```
```public class Solution {

//This solution counts the number of strings consisting of sorted vowels

public int CountVowelStrings(int n) {

//Base case
if (n == 1) return 5;

//Recursive case
return 5 * CountVowelStrings(n - 1) - CountVowelStrings(n - 2);
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]