Count Sorted Vowel Strings - Leetcode Solution

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.

1