Count Sorted Vowel Strings

Medium
317.

Count Sorted Vowel Strings

Count Sorted Vowel Strings is a medium coding problem on dynamic programming, math and combinatorics, asked in Amazon and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Sorted means the choice at each position is limited to the current letter or a later one.

  2. Hint 2

    Let dp[v] be the number of valid suffixes that start with vowel v; extending the length turns it into a suffix sum.

  3. Hint 3

    Closed form: the answer is C(n + 4, 4) — the number of ways to split n positions 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

  1. Start dp = [1, 1, 1, 1, 1].
  2. Repeat n - 1 times: for i from 3 down to 0, dp[i] += dp[i+1].
  3. 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