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[1][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[1][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][5];
        // there is only one string of length 1
        for (int j = 0; j < 5; j++) {
            dp[1][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) {
            set.add(curr);
        } 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); 
} 
}