1220. Count Vowels Permutation

📝 Problem Details

• Title: 1220. Count Vowels Permutation
• Link: https://leetcode.com/problems/count-vowels-permutation/
• Difficulty: Hard
• Tags/Categories: Dynamic-Programming

💭What Were My Initial Thoughts?

- the number of possible permutations grows exponentially with the length of the sequence n
- brute force would be to generate all possible vowel sequences of length n and check each sequence to see if it satisfies the given rules for valid transitions between vowels
- many sequences share the same suffix or prefix sequence 
- dynamic programming seems like the appropriate approach since we can store and reuse calculations for overlapping subproblems (sequences)

🤔What Did I Struggle With?

- implementing the storage of overlapping subproblems
- accurately defining the subproblem

💡 Explanation of Solution

- create a matrix `dp` where dp[i][v] represent the number of valid strings of length i that end with the vowel v

1. Define the transitions based on the rules
	- dp[i+1][a] = dp[i][e] + dp[i][u] + dp[i][i]
	- dp[i+1][e] = dp[i][a] + dp[i][i]
	- dp[i+1][i] = dp[i][e] + dp[i][o]
	- dp[i+1][o] = dp[i][i]
	- dp[i+1][u] = dp[i][o] + dp[i][i]

2. Base case: at i=1, dp[1][v] for each vowel v, as a single character string can be any vowel

3. Iterate for n: Compute dp[i][v] for all vowels at each string length i up to n

4. Sum the results: The answer is the sum of dp[n][a],   dp[n][e],   dp[n][i],   dp[n][o],   dp[n][u]

5. Optimization: since dp[i] depends only on dp[i-1] we can resuce the space complexity of this solution to constant O(1) by keeping only the current and previous states

⌛ Complexity Analysis

Time Complexity : O(n) since we only iterate through the length of the string
Space Complexity: O(1) since we are using a fixed number of variables to store intermediate results

💻 Implementation of Solution

const int MOD = 1e9 + 7;
 
int countVowelPermutation(int n) {
	// initialize the dp array for the vowels a,e,i,o.u
	vector<long long> dp(5,1); // base case for length 1, each vowel should only have 1 possible permutation
 
	// start at i=2 since we already cover the base case of i=1 above
	for(int i=2; i <= n; i++) {
		vector<long, long> newDp(5,0);
		//update dp based on the rules
		newDp[0] = (dp[1] + dp[2] + dp[4]) % MOD; // 'a' -> 'e', 'i', 'u'
		newDp[1] = (dp[0] + dp[2]) % MOD; // 'e' -> 'a', 'i'
		newDp[2] = (dp[1] + dp[3]) % MOD; // 'i' -> 'e', 'o'
		newDp[3] = dp[2] % MOD; // 'o' -> 'i'
		newDp[4] = (dp[2] + dp[3]) % MOD; // 'u' -> 'i', 'o'
		dp = newDp; // move to the next iteration
	}
	// sum up all the counts for strings of length n
	long long result = 0;
	for(long long count : dp) {
		result = (result + count) % MOD;
	}
 
	return result;
}