_1641.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.Arrays;

publicclass_1641 {
publicstaticclassSolution1 {
/*
 * I solved this problem using Math, no DP, recursion or backtracking techniques.
 * Time: beat 100% submission consistently since it's O(n), essentialy it's O(1) because the contraints in the problem state: 1 <= n <= 50
 * After writing out from n = 1 to 3, we can see the pattern.
 * Detailed reasoning to be seen in my YouTube video on my channel: https://youtu.be/gdH4yfgfwiU
 */
publicintcountVowelStrings(intn) {
if (n == 1) {
return5;
 }
int[] arr = newint[] {1, 1, 1, 1, 1};
intsum = 5;
for (inti = 2; i <= n; i++) {
int[] copy = newint[5];
for (intj = 0; j < arr.length; j++) {
if (j == 0) {
copy[j] = sum;
 } else {
copy[j] = copy[j - 1] - arr[j - 1];
 }
 }
arr = Arrays.copyOf(copy, 5);
sum = 0;
for (intj = 0; j < arr.length; j++) {
sum += arr[j];
 }
 }
returnsum;
 }
 }
}