2 minutes

# Leetcode 1641

Count Sorted Vowel Strings

## 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[5];
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];
// follow the pattern :)
// i was giving i-1 and
// was really confused
}
}
int result = 0;
for(int i = 0; i < store.length; i++)
result += store[i];
return result;
}
```