Count Sorted Vowel Strings — Solution in Python, Java & C++
Count Sorted Vowel Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Sorted Vowel Strings is a medium coding problem on dynamic programming, math and combinatorics, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return the number of strings of length n that consist only of the vowels a, e, i, o and u and are lexicographically sorted — every letter is greater than or equal to the one before it.
Example 1
Input: n = 1
Output: 5
Explanation: The five single vowels.
Example 2
Input: n = 2
Output: 15
Example 3
Input: n = 33
Output: 66045
Constraints
1 <= n <= 50
Hints for Count Sorted Vowel Strings
Hint 1
Sorted means the choice at each position is limited to the current letter or a later one.
Hint 2
Let
dp[v]be the number of valid suffixes that start with vowelv; extending the length turns it into a suffix sum.Hint 3
Closed form: the answer is
C(n + 4, 4)— the number of ways to splitnpositions among 5 vowels.
How to solve Count Sorted Vowel Strings
Let dp[v] be the number of sorted strings of the current length starting with vowel v; adding a position turns it into a suffix sum.
Approach
- Start
dp = [1, 1, 1, 1, 1]. - Repeat
n - 1times: forifrom 3 down to 0,dp[i] += dp[i+1]. - Return the sum.
Why it works
A sorted string starting with vowel v continues with a sorted string starting with v or later, so each length step replaces dp[v] by Σ dp[w] for w ≥ v. Updating right to left keeps the previous length's values available.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The closed form is
C(n + 4, 4)— stars and bars over five vowels.
Reference solution
Python
def countVowelStrings(n: int) -> int:
dp = [1] * 5
for _ in range(n - 1):
for i in range(3, -1, -1):
dp[i] += dp[i + 1]
return sum(dp)Java
public static int countVowelStrings(int n) {
int[] dp = {1, 1, 1, 1, 1};
for (int step = 1; step < n; step++) {
for (int i = 3; i >= 0; i--) dp[i] += dp[i + 1];
}
return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
}C++
int countVowelStrings(int n) {
int dp[5] = {1, 1, 1, 1, 1};
for (int step = 1; step < n; step++) {
for (int i = 3; i >= 0; i--) dp[i] += dp[i + 1];
}
return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
}JavaScript
var countVowelStrings = function(n) {
const dp = [1, 1, 1, 1, 1];
for (let step = 1; step < n; step++) {
for (let i = 3; i >= 0; i--) dp[i] += dp[i + 1];
}
return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming