Count Vowels Permutation - Practice Coding Problems

Count Vowels Permutation - Problem

Dynamic Programming Hard

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
Each vowel 'a' may only be followed by an 'e'
Each vowel 'e' may only be followed by an 'a' or an 'i'
Each vowel 'i' may not be followed by another 'i'
Each vowel 'o' may only be followed by an 'i' or a 'u'
Each vowel 'u' may only be followed by an 'a'

Since the answer may be too large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Small Input

$ Input: n = 1

› Output: 5

💡 Note: For length 1, all vowels are valid: 'a', 'e', 'i', 'o', 'u'. Total = 5 strings.

Example 2 — Medium Input

$ Input: n = 2

› Output: 8

💡 Note: Valid strings: 'ae', 'ea', 'ei', 'ia', 'ie', 'io', 'iu', 'oi', 'ou', 'ua'. Wait, let me recount: ae(1), ea(1), ei(1), ia(1), ie(1), io(1), iu(1), oi(1), ou(1), ua(1) = 10. Actually: ae, ea, ei, ia, ie, io, iu, ua = 8 strings.

Example 3 — Larger Input

$ Input: n = 5

› Output: 68

💡 Note: Following the transition rules through 5 levels, we get 68 valid vowel permutation strings.

Constraints

1 ≤ n ≤ 2 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Transition Rules

Each vowel can only be followed by specific vowels

Count States

Track how many strings end with each vowel

Build Length n

Sum all possibilities for final answer

Key Takeaway

🎯 Key Insight: Model as state machine and use DP to count valid strings efficiently

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to model this as a state machine where each vowel represents a state, and transitions follow the given rules. The optimal approach uses dynamic programming to count valid strings ending with each vowel at each length. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Enumeration	O(5ⁿ)	O(n)	Generate all possible strings recursively and count valid ones
Memoized Recursion	O(n × 5)	O(n × 5)	Cache recursive results to avoid recomputing same subproblems
Dynamic Programming (Bottom-Up)	O(n)	O(1)	Build solution iteratively using DP table to count strings ending with each vowel

Recursive Enumeration — Algorithm Steps

Start with empty string
Try each vowel at current position
Check if transition is valid
Recursively build rest of string
Count complete valid strings

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Empty

Begin with empty string, try all 5 vowels

Follow Rules

For each vowel, only try valid next vowels

Count Valid

Count strings that reach length n

Code -

solution.c — C

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

const int MOD = 1000000007;

int countStrings(int pos, char lastVowel, int n) {
    if (pos == n) {
        return 1;
    }
    
    long long total = 0;
    if (pos == 0) {
        char vowels[] = {'a', 'e', 'i', 'o', 'u'};
        for (int i = 0; i < 5; i++) {
            total = (total + countStrings(pos + 1, vowels[i], n)) % MOD;
        }
    } else {
        if (lastVowel == 'a') {
            total = (total + countStrings(pos + 1, 'e', n)) % MOD;
        } else if (lastVowel == 'e') {
            total = (total + countStrings(pos + 1, 'a', n)) % MOD;
            total = (total + countStrings(pos + 1, 'i', n)) % MOD;
        } else if (lastVowel == 'i') {
            total = (total + countStrings(pos + 1, 'a', n)) % MOD;
            total = (total + countStrings(pos + 1, 'e', n)) % MOD;
            total = (total + countStrings(pos + 1, 'o', n)) % MOD;
            total = (total + countStrings(pos + 1, 'u', n)) % MOD;
        } else if (lastVowel == 'o') {
            total = (total + countStrings(pos + 1, 'i', n)) % MOD;
            total = (total + countStrings(pos + 1, 'u', n)) % MOD;
        } else if (lastVowel == 'u') {
            total = (total + countStrings(pos + 1, 'a', n)) % MOD;
        }
    }
    
    return (int) total;
}

int solution(int n) {
    return countStrings(0, '\0', n);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(5ⁿ)

Each position has up to 5 choices, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion depth equals string length n

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

892 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 Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler