Scale Engineer

Count Sorted Vowel Strings

Med
#1507Time: Exponential - The time complexity is roughly O(k^n) where k is the number of vowels (5). The function branches for each position in the string, leading to an exponential number of calls. This is too slow for the given constraints.Space: O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.
Patterns
MathDynamic ProgrammingCombinatorics

Prompt

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:

["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 

Approaches

4 approaches with complexity analysis and trade-offs.

A straightforward approach is to use backtracking to generate all possible sorted vowel strings of length n and count them. We can build the strings character by character, ensuring that each new character is greater than or equal to the previous one. This naturally leads to a recursive solution.

Algorithm

  1. Define a recursive function, let's call it generateAndCount, that takes the current string length n and the index of the last vowel used lastVowelIndex.
  2. The lastVowelIndex helps ensure the lexicographical order. For the next character, we can only pick vowels from lastVowelIndex onwards.
  3. The base case for the recursion is when the desired length n is reached. In this case, we have found one valid string, so we return 1.
  4. In the recursive step, we iterate through the vowels starting from lastVowelIndex. For each vowel, we make a recursive call for a string of length n-1, passing the current vowel's index.
  5. The total count is the sum of the results from all these recursive calls.
  6. The initial call would be to a helper function that starts the process for length n and allows any vowel to be the first character.

Walkthrough

We can define a recursive function that builds the string. The state of our recursion can be defined by (current_length, last_vowel_index). The current_length tracks the length of the string built so far, and last_vowel_index tracks the last vowel added to maintain the sorted order. The function would explore adding all valid subsequent vowels. When the current_length reaches n, we've successfully constructed one valid string and increment our total count.

class Solution {    public int countVowelStrings(int n) {        return count(n, 0);    }     private int count(int length, int lastVowelIndex) {        // Base case: if a string of the desired length is formed, we found one valid string.        if (length == 0) {            return 1;        }         int total = 0;        // Iterate through the vowels that can be placed at the current position.        // To maintain lexicographical order, the next vowel must be the same as or come after the last one.        for (int i = lastVowelIndex; i < 5; i++) {            total += count(length - 1, i);        }        return total;    }}

Complexity

Time

Exponential - The time complexity is roughly O(k^n) where k is the number of vowels (5). The function branches for each position in the string, leading to an exponential number of calls. This is too slow for the given constraints.

Space

O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • It's a direct translation of the problem's constraints into code.

Cons

  • Extremely inefficient due to a large number of redundant calculations.

  • Will result in a 'Time Limit Exceeded' (TLE) error for larger values of n (like n > 15).

Solutions

class Solution { private Integer [][] f ; private int n ; public int countVowelStrings ( int n ) { this . n = n ; f = new Integer [ n ][ 5 ]; return dfs ( 0 , 0 ); } private int dfs ( int i , int j ) { if ( i >= n ) { return 1 ; } if ( f [ i ][ j ] != null ) { return f [ i ][ j ]; } int ans = 0 ; for ( int k = j ; k < 5 ; ++ k ) { ans += dfs ( i + 1 , k ); } return f [ i ][ j ] = ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem