1641. Count Sorted Vowel Strings


Problem Description

The goal is to find the number of strings of a given length n that are composed solely of vowels (a, e, i, o, u) and are lexicographically sorted. A lexicographically sorted string means that each character in the string is in non-decreasing alphabetical order. For example, the string "aei" is sorted but "aie" is not because i comes before e alphabetically. Given that the strings can only contain vowels, and they must be in sorted order, we have to count all the possible combinations that meet these criteria for a string of length n.

Intuition

To understand the solution, let's consider a simple case with n = 1. There are obviously 5 strings that can be formed, each with one character: a, e, i, o, or u. Now consider n = 2. We can add each vowel to each of the strings of length 1, but because our strings must remain sorted, every character we add can only be the same or come after the character in our existing string. So for 'a', we can add a, e, i, o, or u, but for 'e', we can only add e, i, o, or u, and so on. This results in a total of 15 strings.

Intuitively, you can see that the problem is related to the concept of combinations with repetitions allowed. The code provided uses a dynamic programming approach to build a solution for a string of length n based on the solutions for strings of length n-1. Here's how the implementation works:

  1. We start by initializing a list f with length 5, filled with 1s. This list keeps track of the number of ways to end a string of length n with each vowel. Initially, for the case where n = 1, we have 1 way to end a string with each vowel.

  2. For each additional character in our string (from 2 to n), we iterate through our list f, and for each position, we calculate the cumulative sum up to the current position. This cumulative sum represents the number of ways we can form a string of the current length that ends with the vowel corresponding to the current position.

  3. Why does this work? The cumulative sum works because it adds all the ways we could form strings ending with vowels that can lexicographically precede the current vowel. This is exactly what we need because earlier vowels can always be followed by later vowels to maintain the sorted order.

  4. After we have iterated through all the characters (n - 1 times), we sum up our list f to get the total number of sorted vowel strings of length n.

The elegance of the solution lies in the way it builds from simpler subproblems, exploiting the fact that every subproblem is related to smaller instances of itself; hence, building up to the solution rather than trying to compute it from scratch.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The solution uses dynamic programming, a common technique for solving problems by breaking them down into simpler subproblems. The Python code's structure demonstrates how we can smartly leverage the combinatorial nature of the problem with a bottom-up approach. Here's a step-by-step walkthrough of how the algorithm operates:

  1. Initialize the State: A list f of length 5 is initialized with ones, f = [1, 1, 1, 1, 1]. This represents the number of ways to form a lexicographically sorted string with n = 1 for each vowel. Essentially, these are the base cases.

  2. Iterate Over String Length: We iterate from 2 up to n (since n = 1 is our base case). For each new length, we are trying to compute the number of sorted vowel strings of that length.

  3. Update State with Cumulative Sums: For each vowel indexed by j, we update f[j] with the sum of counts up to j. In other words, s is a running total which is added to each f[j]. This represents all the ways we can end a string with the vowel at f[j] while maintaining lexicographic order.

    • For example, if f currently equals [1, 2, 3, 4, 5] (for 'a', 'e', 'i', 'o', 'u' respectively), for the next length, 'a' can be followed by any vowel so it takes the sum of all possibilities [1+2+3+4+5]. 'e' cannot be followed by 'a', so it gets [2+3+4+5], and so on.
  4. Final Summation: Once all iterations for lengths are completed, we sum up all the numbers in f to get the total count of valid lexicographically sorted strings of length n.

This solution effectively applies the principles of counting sort by accumulating the number of valid previous options and using them to form new strings. By the end of the iterations, sum(f) gives us the desired output — the number of lexicographically sorted strings of length n.

Here's how the code encapsulates this logic:

1class Solution:
2    def countVowelStrings(self, n: int) -> int:
3        f = [1] * 5  # Base case initialization
4        for _ in range(n - 1): # Iterating over string length
5            s = 0  # Reset cumulative sum
6            for j in range(5): # Iterating over vowels
7                s += f[j]  # Cumulative sum represents the combinatorial options
8                f[j] = s  # Store the new count back in f
9        return sum(f)  # Final result is the sum of the last state

The algorithm's time and space complexity are both O(N), where N is the length of the string, making it efficient even for larger strings as it only requires iterating and updating a 5-element list N-1 times.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Let's illustrate the solution approach with an example where n = 3, i.e., we want to find the count of all lexicographically sorted strings that can be formed using vowels and have a length of 3.

  1. Initialize the State: We start by setting f = [1, 1, 1, 1, 1], which represents there is 1 way to create a string of length 1 ending with each of the vowels 'a', 'e', 'i', 'o', 'u'.

  2. Iterate Over String Length:

    • For n = 2:

      • We start by initializing a cumulative sum s = 0.
      • We then update this sum in a loop for each element in f:
        • For 'a' (f[0]), the sum becomes s = 0 + 1 = 1; we update f[0] = 1.
        • For 'e' (f[1]), the sum becomes s = 1 + 1 = 2; we update f[1] = 2.
        • For 'i' (f[2]), the sum becomes s = 2 + 1 = 3; we update f[2] = 3.
        • For 'o' (f[3]), the sum becomes s = 3 + 1 = 4; we update f[3] = 4.
        • For 'u' (f[4]), the sum becomes s = 4 + 1 = 5; we update f[4] = 5.
      • Now, f = [1, 2, 3, 4, 5] after the first pass which accounts for strings of length 2.
    • For n = 3:

      • Again, we initialize the cumulative sum s = 0.
      • We repeat the loop, updating f cumulatively:
        • For 'a', 's' becomes s = 0 + 1 = 1; 'a' can precede any vowels, so we keep f[0] = 1.
        • For 'e', 's' becomes s = 1 + 2 = 3; 'e' can only be followed by 'e', 'i', 'o', 'u', so f[1] = 3.
        • For 'i', 's' becomes s = 3 + 3 = 6; 'i' can only be followed by 'i', 'o', 'u', so f[2] = 6.
        • For 'o', 's' becomes s = 6 + 4 = 10; 'o' can only be followed by 'o', 'u', so f[3] = 10.
        • For 'u', 's' becomes s = 10 + 5 = 15; 'u' can only be followed by 'u', so f[4] = 15.
      • Our array f is now [1, 3, 6, 10, 15].
  3. Final Summation: After completing iteration for n = 3, we calculate the sum of all elements in f to obtain the total count of sorted vowel strings of length n:

    • sum = 1 + 3 + 6 + 10 + 15 = 35

Therefore, the number of lexicographically sorted strings of length 3 that can be made using the vowels 'a', 'e', 'i', 'o', 'u' is 35. This example demonstrates how the dynamic programming approach simplifies the counting process by breaking it down into manageable steps, building upon the result for each previous length to gradually find the total count for a string of length n.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Python Solution

1class Solution:
2    def countVowelStrings(self, n: int) -> int:
3        # Initialize a list `vowel_count` with 5 elements all set to 1.
4        # This represents the count for each vowel: a, e, i, o, u
5        vowel_count = [1] * 5
6      
7        # We loop over `n - 1` times because we already initialized the first set of counts.
8        for _ in range(n - 1):
9            # Initialize a running sum to build the counts for the current position.
10            running_sum = 0
11            # Loop through the counts for each vowel.
12            for j in range(5):
13                # Add the count for the current vowel to the running sum.
14                running_sum += vowel_count[j]
15                # Update the count for the current vowel with the running sum.
16                # This step is based on the dynamic programming principle, where
17                # the count of vowel strings ending with the current vowel is equal to
18                # all vowel strings ending with any vowel up to the current one.
19                vowel_count[j] = running_sum
20      
21        # Return the sum of all counts, which represents all possible vowel strings of length `n`.
22        return sum(vowel_count)
23

Java Solution

1import java.util.Arrays;  // Import the Arrays class for the sum method
2
3class Solution {
4  
5    // This method counts the number of strings consisting of vowels that can be formed of length `n`.
6    public int countVowelStrings(int n) {
7        // An array to represent the counts of vowel strings for each vowel ending
8        // f[0] for 'a', f[1] for 'e', f[2] for 'i', f[3] for 'o', f[4] for 'u'
9        int[] vowelCounts = {1, 1, 1, 1, 1};
10      
11        // Loop over the length n times, first length is already initialized, so we start from 0 to n-2
12        for (int i = 0; i < n - 1; ++i) {
13            // A temporary variable to keep track of the cumulative sum
14            int cumulativeSum = 0;
15            // This loop calculates the new counts by adding up counts from all previous vowels
16            for (int j = 0; j < 5; ++j) {
17                // Update cumulative sum with the current vowel count
18                cumulativeSum += vowelCounts[j];
19                // Update the count for the current vowel with the new cumulative sum
20                vowelCounts[j] = cumulativeSum;
21            }
22        }
23        // Sum up all the counts and return the result
24        return Arrays.stream(vowelCounts).sum();
25    }
26}
27

C++ Solution

1#include <numeric> // Required for std::accumulate
2
3class Solution {
4public:
5    int countVowelStrings(int n) {
6        // Initialize an array with 5 elements corresponding to the 5 vowels
7        // and assign them the base case value, which is 1 for each vowel.
8        int vowelCounts[5] = {1, 1, 1, 1, 1};
9      
10        // Run the loop for 'n - 1' times starting from 0 since the base case
11        // for the first element is already set.
12        for (int i = 0; i < n - 1; ++i) {
13            // Initialize the sum which holds the running number of strings
14            // ending with the current vowel.
15            int runningSum = 0;
16          
17            // Iterate through the vowelCounts to update the counts for each vowel.
18            // To prevent the new updates for vowels as we progress through the arrays,
19            // we utilize the runningSum to keep track of the updated counts.
20            for (int j = 0; j < 5; ++j) {
21                // Add the current vowel's count to the running sum.
22                runningSum += vowelCounts[j];
23              
24                // Update the count for the current vowel to be the running sum,
25                // which is effectively the count of vowel strings ending with the
26                // current vowel or before.
27                vowelCounts[j] = runningSum;
28            }
29        }
30      
31        // Return the sum of all the vowel string counts which we have
32        // accumulated in our vowelCounts array for 'n' positions.
33        // std::accumulate performs a fold operation over the entire range
34        // [first, last) and the initial sum value of 0. 
35        return std::accumulate(vowelCounts, vowelCounts + 5, 0);
36    }
37};
38

Typescript Solution

1/**
2 * Count the number of strings of length `n` composed of vowels (a, e, i, o, u)
3 * that are lexicographically sorted.
4 * 
5 * @param {number} n - The length of the vowel strings to count.
6 * @returns {number} - The total count of lexicographically sorted vowel strings.
7 */
8function countVowelStrings(n: number): number {
9    // Initialize an array with 5 elements corresponding to the counts for a, e, i, o, u.
10    let vowelCounts: number[] = [1, 1, 1, 1, 1];
11  
12    // Loop for 'n - 1' times since we start the counts with the base case of length 1.
13    for (let i = 0; i < n - 1; i++) {
14        // Initialize the running sum, which holds the cumulative counts.
15        let runningSum = 0;
16      
17        // Update the counts for each position in the vowel string.
18        for (let j = 0; j < 5; j++) {
19            // Update the running sum with the current vowel count.
20            runningSum += vowelCounts[j];
21          
22            // Assign the running sum as the new vowel count for the current vowel.
23            // This represents the total count of strings ending with this vowel or before.
24            vowelCounts[j] = runningSum;
25        }
26    }
27  
28    // Calculate and return the total count of vowel strings of length `n`.
29    // Use the reduce function to sum all elements in `vowelCounts`.
30    return vowelCounts.reduce((acc, count) => acc + count, 0);
31}
32
Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Time and Space Complexity

The given Python code is used to count the number of strings of length n that consist only of vowels (a, e, i, o, u), where each string is lexicographically greater than the previous one (i.e., we can consider each vowel as a number, and these strings represent non-decreasing sequences).

Time Complexity

To analyze the time complexity, we observe the following steps in the code:

  1. An initial list f is created with 5 elements, all of which are set to 1. This represents the number of vowel strings of length 1.

  2. The outer loop runs (n - 1) times which is O(n) since n is the length of the string to be formed.

  3. Inside the outer loop, there is an inner loop that iterates over the 5 vowels.

  4. For each vowel, it accumulates the values from the previous counts in the list f, effectively computing the cumulative sum.

Since there are 5 vowels, the inner loop runs at constant time, O(5), which simplifies to O(1). The cumulative sum in the inner loop does not alter the time complexity.

Thus, combining the complexity of the outer and inner loop, the final time complexity comes out to be O(n) * O(1) = O(n).

Space Complexity

The space complexity is determined by the storage utilized by the algorithm which remains constant irrespective of the input size:

  1. A list f containing 5 elements is used to store the count of each type of vowel strings ending in a particular vowel, which takes up constant space O(5).

  2. The variable s is used to keep the cumulative sum within the inner loop. This is just an integer, which also uses constant space O(1).

Therefore, the space complexity of the algorithm is O(5) + O(1), which simplifies to O(1) indicating constant space complexity.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫