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.

Examples

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

Solution

Method 1 – Backtracking (Brute Force)

Intuition

Generate all possible strings of length n using vowels, ensuring each character is not less than the previous one (to maintain lexicographical order). This is a classic backtracking problem where we try all valid choices at each step.

Approach

1. Define a recursive function that:
   • Takes the remaining length n and the last chosen vowel index.
   • For each vowel index from the last chosen to the end, recursively build the string.
2. Base case: If n is 0, increment the answer.
3. Start recursion with n and the first vowel index (0).
4. Return the total count.

Code

C++

class Solution {
public:
	 int countVowelStrings(int n) {
		  int ans = 0;
		  function<void(int, int)> dfs = [&](int rem, int last) {
				if (rem == 0) {
					 ans++;
					 return;
				}
				for (int i = last; i < 5; ++i) {
					 dfs(rem - 1, i);
				}
		  };
		  dfs(n, 0);
		  return ans;
	 }
};

Go

func countVowelStrings(n int) int {
	 var ans int
	 var dfs func(int, int)
	 dfs = func(rem, last int) {
		  if rem == 0 {
				ans++
				return
		  }
		  for i := last; i < 5; i++ {
				dfs(rem-1, i)
		  }
	 }
	 dfs(n, 0)
	 return ans
}

Java

class Solution {
	 public int countVowelStrings(int n) {
		  int[] ans = new int[1];
		  dfs(n, 0, ans);
		  return ans[0];
	 }
	 private void dfs(int rem, int last, int[] ans) {
		  if (rem == 0) {
				ans[0]++;
				return;
		  }
		  for (int i = last; i < 5; i++) {
				dfs(rem - 1, i, ans);
		  }
	 }
}

Kotlin

class Solution {
	 fun countVowelStrings(n: Int): Int {
		  var ans = 0
		  fun dfs(rem: Int, last: Int) {
				if (rem == 0) {
					 ans++
					 return
				}
				for (i in last until 5) {
					 dfs(rem - 1, i)
				}
		  }
		  dfs(n, 0)
		  return ans
	 }
}

Python

class Solution:
	 def countVowelStrings(self, n: int) -> int:
		  ans: int = 0
		  def dfs(rem: int, last: int) -> None:
				nonlocal ans
				if rem == 0:
					 ans += 1
					 return
				for i in range(last, 5):
					 dfs(rem - 1, i)
		  dfs(n, 0)
		  return ans

Rust

impl Solution {
	 pub fn count_vowel_strings(n: i32) -> i32 {
		  fn dfs(rem: i32, last: usize, ans: &mut i32) {
				if rem == 0 {
					 *ans += 1;
					 return;
				}
				for i in last..5 {
					 dfs(rem - 1, i, ans);
				}
		  }
		  let mut ans = 0;
		  dfs(n, 0, &mut ans);
		  ans
	 }
}

Complexity

• ⏰ Time complexity: O(5^n)
• 🧺 Space complexity: O(n) for recursion stack

Method 2 – Top Down Dynamic Programming (Memoization)

Intuition

The problem has overlapping subproblems and optimal substructure, making it suitable for dynamic programming. For each position in the string, we can choose any vowel that is not less than the previous one, and we can cache results for subproblems defined by the remaining length and the current vowel index.

Approach

1. Define a recursive function dfs(rem, last) where:
   • rem is the number of characters left to fill.
   • last is the index of the last vowel used (to ensure lexicographical order).
2. For each call, try all vowels from last to 4 (since vowels are ordered as a, e, i, o, u).
3. Use a 2D DP array to memoize results for each (rem, last) pair.
4. Base case: If rem == 0, return 1 (a valid string is formed).
5. Sum results for all valid choices and store in DP.
6. Start recursion with rem = n and last = 0.

Code

C++

class Solution {
public:
	 int countVowelStrings(int n) {
		  int dp[51][5] = {};
		  function<int(int, int)> dfs = [&](int rem, int last) {
				if (rem == 0) return 1;
				if (dp[rem][last]) return dp[rem][last];
				int ans = 0;
				for (int i = last; i < 5; ++i) {
					 ans += dfs(rem - 1, i);
				}
				return dp[rem][last] = ans;
		  };
		  return dfs(n, 0);
	 }
};

Go

func countVowelStrings(n int) int {
	 var dp [51][5]int
	 var dfs func(int, int) int
	 dfs = func(rem, last int) int {
		  if rem == 0 {
				return 1
		  }
		  if dp[rem][last] != 0 {
				return dp[rem][last]
		  }
		  ans := 0
		  for i := last; i < 5; i++ {
				ans += dfs(rem-1, i)
		  }
		  dp[rem][last] = ans
		  return ans
	 }
	 return dfs(n, 0)
}

Java

class Solution {
	 public int countVowelStrings(int n) {
		  int[][] dp = new int[n + 1][5];
		  return dfs(n, 0, dp);
	 }
	 private int dfs(int rem, int last, int[][] dp) {
		  if (rem == 0) return 1;
		  if (dp[rem][last] != 0) return dp[rem][last];
		  int ans = 0;
		  for (int i = last; i < 5; i++) {
				ans += dfs(rem - 1, i, dp);
		  }
		  dp[rem][last] = ans;
		  return ans;
	 }
}

Kotlin

class Solution {
	 fun countVowelStrings(n: Int): Int {
		  val dp = Array(n + 1) { IntArray(5) }
		  fun dfs(rem: Int, last: Int): Int {
				if (rem == 0) return 1
				if (dp[rem][last] != 0) return dp[rem][last]
				var ans = 0
				for (i in last until 5) {
					 ans += dfs(rem - 1, i)
				}
				dp[rem][last] = ans
				return ans
		  }
		  return dfs(n, 0)
	 }
}

Python

class Solution:
	 def countVowelStrings(self, n: int) -> int:
		  dp: list[list[int]] = [[0] * 5 for _ in range(n + 1)]
		  def dfs(rem: int, last: int) -> int:
				if rem == 0:
					 return 1
				if dp[rem][last]:
					 return dp[rem][last]
				ans = 0
				for i in range(last, 5):
					 ans += dfs(rem - 1, i)
				dp[rem][last] = ans
				return ans
		  return dfs(n, 0)

Rust

impl Solution {
	 pub fn count_vowel_strings(n: i32) -> i32 {
		  fn dfs(rem: usize, last: usize, dp: &mut [[i32; 5]]) -> i32 {
				if rem == 0 {
					 return 1;
				}
				if dp[rem][last] != 0 {
					 return dp[rem][last];
				}
				let mut ans = 0;
				for i in last..5 {
					 ans += dfs(rem - 1, i, dp);
				}
				dp[rem][last] = ans;
				ans
		  }
		  let mut dp = [[0; 5]; 51];
		  dfs(n as usize, 0, &mut dp)
	 }
}

Complexity

• ⏰ Time complexity: O(n*5)
• 🧺 Space complexity: O(n*5) for memoization table

Method 3 – Bottom Up Dynamic Programming

Intuition

The key idea is to count the number of lexicographically sorted vowel strings of length n by building up solutions for smaller lengths. For each position, we can only use vowels that are the same or come after the previous vowel. We use a DP table where dp[i][j] represents the number of strings of length i starting with the j-th vowel or any vowel after it.

Approach

1. Initialize a 2D DP table dp of size (n+1) x 5, where dp[i][j] is the number of strings of length i starting with the j-th vowel or later.
2. For length 1 (i = 1), set dp[1][j] = 1 for all vowels j (since each vowel alone is a valid string).
3. For lengths from 2 to n, fill dp[i][j] by summing dp[i-1][j] (strings starting with the same vowel) and dp[i][j+1] (strings starting with a later vowel).
4. The answer is dp[n][0], representing all strings of length n starting with any vowel.

Code

C++

class Solution {
public:
	int countVowelStrings(int n) {
		int dp[n + 1][5] = {};
		for (int j = 0; j < 5; ++j) dp[1][j] = 1;
		for (int i = 2; i <= n; ++i) {
			for (int j = 4; j >= 0; --j) {
				dp[i][j] = dp[i - 1][j] + (j < 4 ? dp[i][j + 1] : 0);
			}
		}
		return dp[n][0];
	}
};

Go

func countVowelStrings(n int) int {
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, 5)
	}
	for j := 0; j < 5; j++ {
		dp[1][j] = 1
	}
	for i := 2; i <= n; i++ {
		for j := 4; j >= 0; j-- {
			if j == 4 {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j] + dp[i][j+1]
			}
		}
	}
	return dp[n][0]
}

Java

class Solution {
	public int countVowelStrings(int n) {
		int[][] dp = new int[n + 1][5];
		for (int j = 0; j < 5; j++) dp[1][j] = 1;
		for (int i = 2; i <= n; i++) {
			for (int j = 4; j >= 0; j--) {
				dp[i][j] = dp[i - 1][j] + (j < 4 ? dp[i][j + 1] : 0);
			}
		}
		return dp[n][0];
	}
}

Kotlin

class Solution {
	fun countVowelStrings(n: Int): Int {
		val dp = Array(n + 1) { IntArray(5) }
		for (j in 0..4) dp[1][j] = 1
		for (i in 2..n) {
			for (j in 4 downTo 0) {
				dp[i][j] = dp[i - 1][j] + if (j < 4) dp[i][j + 1] else 0
			}
		}
		return dp[n][0]
	}
}

Python

class Solution:
	def countVowelStrings(self, n: int) -> int:
		dp: list[list[int]] = [[0] * 5 for _ in range(n + 1)]
		for j in range(5):
			dp[1][j] = 1
		for i in range(2, n + 1):
			for j in range(4, -1, -1):
				dp[i][j] = dp[i - 1][j] + (dp[i][j + 1] if j < 4 else 0)
		return dp[n][0]

Rust

impl Solution {
	pub fn count_vowel_strings(n: i32) -> i32 {
		let n = n as usize;
		let mut dp = vec![vec![0; 5]; n + 1];
		for j in 0..5 {
			dp[1][j] = 1;
		}
		for i in 2..=n {
			for j in (0..5).rev() {
				dp[i][j] = dp[i - 1][j] + if j < 4 { dp[i][j + 1] } else { 0 };
			}
		}
		dp[n][0]
	}
}

Complexity

• ⏰ Time complexity: O(n*k), where k = 5(number of vowels)
• 🧺 Space complexity: O(n*k)

Dry Run

A useful pattern here is that adding 'a' to every string of length n-1 preserves lexicographic order, and likewise, 'e' can be added to strings that start with 'e' or any vowel after it. For example, when n = 3:

n	a	e	i	o	u
1	5	4	3	2	1
2	15	10	6	3	1
3	35	20	10	4	1

For n = 1, there is 1 string starting with 'u', 2 with 'o' (counting those starting with 'u'), and so forth. For n = 2, the count for 'u' is still 1, while for 'o' it is the sum of strings of length 2 starting with 'u' and those of length 1 starting with 'o', and so on. Here, dp[i][j] gives the number of strings of length i that begin with the j-th vowel or any vowel after it. The DP recurrence is:

dp[i][j] = dp[i - 1][j] + dp[i][j + 1]

Method 4 - Maths Solution Using P & C

1. The allowed characters are the five vowels ["a","e","i","o","u"].
2. Lexicographical order means that, once a vowel like e appears at position i, no earlier vowel can appear after any different vowel; for example, strings like eoe, eie, or eae are not valid because after using another vowel, e cannot be used again without breaking the order.
3. Thus, every valid string is made up of consecutive blocks of the same vowel in order, such as aaiiiiu (which can be described as 2a4i1u). The string is uniquely determined by the lengths of these blocks.
4. The problem reduces to counting the ways to distribute n positions among the five vowels in order, which is equivalent to placing 4 separators among n slots.
5. Using the stars and bars method, the number of ways is C(n+4, 4) = (n+1)(n+2)(n+3)(n+4)/24, since the order of blocks is fixed and we divide by 4! to account for indistinguishable separators.

Code

Java

class Solution {
	public int countVowelStrings(int n) {
		return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24;
	}
}

Complexity

• ⏰ Time complexity: O(1)
• 🧺 Space complexity: O(1)