Similar Problems
Similar Problems not available
Count Sorted Vowel Strings - Leetcode Solution
Companies:
LeetCode: Count Sorted Vowel Strings Leetcode Solution
Difficulty: Medium
Topics: math dynamic-programming
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.
Count Sorted Vowel Strings Solution Code
1