1641. Count Sorted Vowel Strings LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1641. Count Sorted Vowel Strings LeetCode Solution with the best time and space complexity. The solution to Count Sorted Vowel Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Sorted Vowel Strings solution in C++
Count Sorted Vowel Strings solution in Java
Count Sorted Vowel Strings solution in Python
Additional Resources

1641. Count Sorted Vowel Strings LeetCode Solution image

Problem Statement of Count Sorted Vowel Strings

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.

Example 3:

Input: n = 33
Output: 66045

Constraints:

1 <= n <= 50

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

1641. Count Sorted Vowel Strings LeetCode Solution in C++

class Solution {
 public:
  int countVowelStrings(int n) {
    // dp[0] := the number of lexicographically sorted string that end in 'a'
    // dp[1] := the number of lexicographically sorted string that end in 'e'
    // dp[2] := the number of lexicographically sorted string that end in 'i'
    // dp[3] := the number of lexicographically sorted string that end in 'o'
    // dp[4] := the number of lexicographically sorted string that end in 'u'
    vector<int> dp(5, 1);

    for (int i = 2; i <= n; ++i) {
      vector<int> newDp(5);
      for (int j = 0; j < 5; ++j)
        for (int k = 0; k <= j; ++k)
          newDp[j] += dp[k];
      dp = std::move(newDp);
    }

    return accumulate(dp.begin(), dp.end(), 0);
  }
};
/* code provided by PROGIEZ */

1641. Count Sorted Vowel Strings LeetCode Solution in Java

class Solution {
  public int countVowelStrings(int n) {
    // dp[0] := the number of lexicographically sorted string that end in 'a'
    // dp[1] := the number of lexicographically sorted string that end in 'e'
    // dp[2] := the number of lexicographically sorted string that end in 'i'
    // dp[3] := the number of lexicographically sorted string that end in 'o'
    // dp[4] := the number of lexicographically sorted string that end in 'u'
    int[] dp = new int[5];
    Arrays.fill(dp, 1);

    for (int i = 2; i <= n; ++i) {
      int[] newDp = new int[5];
      for (int j = 0; j < 5; ++j)
        for (int k = 0; k <= j; ++k)
          newDp[j] += dp[k];
      dp = newDp;
    }

    return Arrays.stream(dp).sum();
  }
}
// code provided by PROGIEZ

1641. Count Sorted Vowel Strings LeetCode Solution in Python

class Solution {
 public:
  int countVowelStrings(int n) {
    return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
  }
};
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents