## Count Sorted Vowel Strings

Head on over here to try the problem for yourself.

Hint says back-tracking, solutions say dynamic programming 😅.

### Back-tracking

#### Algorithm

The goal is to get all sorted combinations of the vowels for a string of length `n`. I set up a `count` variable outside the functions to ensure it stays out of scope for all the recursive calls. The `helper()` function recieves the previous index and remaining charaters. `helper()` loops till 4 (because there are 5 vowels). Everytime, `n==0`, increment `counter`.

#### Code

``````public class solution {
int count = 0;
public int countVowelStrings(int n) {
helper(n,0);
return count;
}

public void helper(int n, int index) {
if(n <= 0) {
count++;
return;
}
for(; index < 5; index++) {
helper(n - 1, index);
// index not decremented because same
// letters are valid
}
}
}
``````

### Dynamic Programming

#### Algorithm

The following pattern explains the intuition behind this approach.

a e i o u
n = 1 1 1 1 1
n = 2 5 4 3 2 1
n = 3 15 10 6 3 1
:

The last string will always be `uuuu.. n times`. Every other string will occur count of previous + count of next.

#### Code

``````public int countVowelStrings(int n) {
int[] store = new int;
for(int i = 0; i < store.length; i++)
store[i] = 1;
// This is the base condition when n = 1
// so we check for n > 1 in the while
while(n-- > 1) {
for(int i = 3; i >= 0; i--) {
store[i] += store[i+1];