LeetCode — Count Sorted Vowel Strings
Problem Link: https://leetcode.com/problems/count-sorted-vowel-strings/
Problem Description: 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.
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"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.
Approach Used: Dynamic Programming, Recursion
Explanation: In this problem, we want to find the number of strings of the given length (provided as input) such that they consist of only vowels and are lexicographically sorted(in alphabetic order). The alphabets can be repeated any number of times as long as they don’t violate the above-mentioned condition. Since we don’t need to find the actual string, but only their count we don’t require to store the string or do any modification to any string variable.
Now coming to the logic for the solution, We can build logic for kth length if we know the number of strings of length k-1 starting with each vowel. Now suppose we need to make a string of length 3, and the current character is ‘i’, then we know that with this character can only be added as the first character to strings of length 2 which follows the conditions of the question and start with either ‘i’(repetition allowed) or ‘o’ and ‘u’ (lexicographically smaller). Similarly, for a string to start with ‘e’, the curr_length-1 string can start with [‘e’,’i’,’o’,’u’]. So for the current position, we find substrings by placing all the vowels at the current position and then recursively finding for length-1 with all the characters which are lexicographically equal or smaller. Since there will be a lot of recurring subproblems (for e.g. for n=3, subproblem(n=2, char=’u’, will be calculated 5 times (1 time for each vowel)). So we will use a matrix to store the results of previous states. And hence make this recursive solution into a dynamic programming solution.
Code: (Java)
public int countVowelRecursive(int n, int charIndex, int dp[][]){
for(int i=0; i<5; i++){
//if length is 1, then we know the solution
if(n==1)
dp[0][i]=1;
//if we haven't calculated the solution for this subproblem yet
else if(dp[n-2][i]==-1){
dp[n-2][i]=countVowelRecursive(n-1, i, dp);
}
}
//if length 1, then no need to proceed further
if(n==1)
return 1;
int ans=0;
//0 represents a
if(charIndex==0){
//with a, the substring can start with all the characters (a,e,i,o,u)
for(int i=0; i<5; i++)
ans+=dp[n-2][i];
}
//1 represents e
else if(charIndex==1){
//with e, the substring can start with 4 characters (e,i,o,u)
for(int i=1; i<5; i++)
ans+=dp[n-2][i];
}
//2 represents i
else if(charIndex==2){
//with i, the substring can start with 3 characters (i,o,u)
for(int i=2; i<5; i++)
ans+=dp[n-2][i];
}
//3 represents o
else if(charIndex==3){
//with o, the substring can start with 2 characters (o,u)
for(int i=3; i<5; i++)
ans+=dp[n-2][i];
}
//4 represents u
else{
//with u, the substring can start with only u
ans+=dp[n-2][4];
}
//return the ans for current alphabet
return ans;
}
public int countVowelStrings(int n) {
//intialize dp with only 5 columns corresponding to each alphabet
//nth length will be in n-1 position
int[][] dp = new int[n][5];//initialize with -1, to signify it is not calculated yet
for(int i=0; i<n; i++)
Arrays.fill(dp[i],-1);//find answer with all 5 alphabets
int ans=0;
for(int i=0; i<5; i++)
ans+=countVowelRecursive(n, i,dp);
//return final ans
return ans;
}
Complexity:
Space Complexity: O(5n)->O(n). Since we make a 2d array of this size for storing previous states. This can be further optimized by taking just a linear array since we only need the immediately previous state for the current state so we don’t need to store all the states result.
Time Complexity: O(5n)->O(n). To compute for all alphabets at all length. Or simply fill all the positions in the 2-d matrix.
Github Link:
https://github.com/siddhaant-jain/LeetCode/blob/master/DailyChallenge/src/CodeFiles/CountSortedVowelStrings.java
