Count Sorted Vowel Strings

MEDIUM

Description

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

Approaches

Checkout 4 different approaches to solve Count Sorted Vowel Strings. Click on different approaches to view the approach and algorithm in detail.

Brute-force Backtracking

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

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.
The lastVowelIndex helps ensure the lexicographical order. For the next character, we can only pick vowels from lastVowelIndex onwards.
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.
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.
The total count is the sum of the results from all these recursive calls.
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.

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 Analysis

Time Complexity: 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 Complexity: O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.

Pros and Cons

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).

Code Solutions

Checking out 3 solutions in different languages for Count Sorted Vowel Strings. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count Sorted Vowel Strings

Patterns:

MathDynamic ProgrammingCombinatorics