Count The Number Of Vowel Strings In Range - 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.

Note: 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.

Example 1:

Input: n = 1 Output: 5 Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:

Input: n = 2 Output: 15 Explanation: The 15 sorted strings that consist of vowels only are ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].

Solution:

Let's first try to understand the problem statement. We need to count all lexicographically sorted strings of length n consisting only of vowels (a, e, i, o, u). For example, if n=2, we need to count the strings ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Here, all the strings are lexicographically sorted.

We can solve this problem using dynamic programming. We define a 2D array dp[i][j] where i is the length of the string and j is the last character of the string. dp[i][j] represents the number of lexicographically sorted strings of length i ending with character j.

If i=1, then dp[i][j]=1 for all j (since there is only one character in the string).

If i>1, then dp[i][j]=sum(dp[i-1][k]) where k<=j. This is because we can append character j to any string of length i-1 that ends with a character less than or equal to j. For example, if we have "ae" (which ends with 'e') and we need to add one more character, we can add either 'a', 'e', 'i', 'o', or 'u'. But we cannot add 'u' since it is greater than 'e' in the alphabet. Hence, we can add 'a', 'e', 'i', or 'o' to get "aea", "aee", "aei", or "aeo", all of which are lexicographically sorted.

The final answer is the sum of dp[n][j] for all j.

Let's implement the above solution in code:

class Solution { public: int countVowelStrings(int n) { int dp[n+1][5]; memset(dp, 0, sizeof(dp)); for(int i=0;i<5;i++) dp[1][i]=1; // Initialize base cases 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 i=0;i<5;i++) ans+=dp[n][i]; return ans; } };

Time Complexity: O(n^2)

Space Complexity: O(n^2)

The above solution is optimal and runs in time for reasonably large values of n.

1