Count Sorted Vowel Strings - Practice Coding Problems

Count Sorted Vowel Strings - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 1

› Output: 5

💡 Note: All single vowel strings are valid: 'a', 'e', 'i', 'o', 'u' are all lexicographically sorted by themselves

Example 2 — Small Length

$ Input: n = 2

› Output: 15

💡 Note: Valid strings include 'aa', 'ae', 'ai', 'ao', 'au', 'ee', 'ei', 'eo', 'eu', 'ii', 'io', 'iu', 'oo', 'ou', 'uu'. Invalid would be 'ea', 'ia', etc.

Example 3 — Larger Case

$ Input: n = 33

› Output: 66045

💡 Note: For n=33, using the mathematical formula C(33+4, 4) = C(37, 4) = 66045 valid sorted vowel strings

Constraints

1 ≤ n ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Given length n, need to count sorted vowel strings

Process

Find combinations where each char ≤ next char

Output

Return count of valid strings

Key Takeaway

🎯 Key Insight: This is equivalent to choosing vowels with repetition - a classic combinatorics problem with O(1) solution

Asked in

G Google 15 a Amazon 12

The key insight is recognizing this as a combinatorics problem equivalent to choosing vowels with repetition where order doesn't matter. The optimal approach uses the mathematical formula C(n+4, 4) for constant time solution. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Generation	O(5^n)	O(n)	Generate all possible vowel strings and count valid ones
Combinatorics Formula	O(1)	O(1)	Use mathematical formula for combinations with repetition
Dynamic Programming	O(n)	O(1)	Use DP to count ways to form sorted strings ending with each vowel

Recursive Generation — Algorithm Steps

Generate all possible vowel combinations
Check each string for lexicographic ordering
Count valid strings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 5^n possible vowel strings

Validate

Check if each string is sorted

Count

Count valid sorted strings

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int count_result = 0;

bool isSorted(char* s) {
    int len = strlen(s);
    for (int i = 0; i < len - 1; i++) {
        if (s[i] > s[i + 1]) {
            return false;
        }
    }
    return true;
}

void generate(char* current, int remaining, char* vowels, int pos) {
    if (remaining == 0) {
        current[pos] = '\0';
        if (isSorted(current)) {
            count_result++;
        }
        return;
    }
    
    for (int i = 0; i < 5; i++) {
        current[pos] = vowels[i];
        generate(current, remaining - 1, vowels, pos + 1);
    }
}

int solution(int n) {
    count_result = 0;
    char vowels[] = {'a', 'e', 'i', 'o', 'u'};
    char current[51];
    generate(current, n, vowels, 0);
    return count_result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(5^n)

Generate 5^n possible strings, each taking O(n) to validate

✓ Linear Growth

Space Complexity

O(n)

Recursion depth is n levels deep

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler