# 1641. Count Sorted Vowel Strings

journey to solution.. :D

**Intuition for DP solution:**

We can generate all possible strings using backtracking. Lets break it into parts.

Let's start with a string of size 2.

Possible letters we have** [a,e,i,o,u]**

if the first letter fixed as **a** then we can pick anyone as second, hence 5 option

Suppose we didn’t pick **a **than next is **e** and for second we have 4 option left.

So we can observe we have two option for every position:

( Suppose length is n )

- use current vowel and solve for length n-1.
- Don’t pick the current vowel. pick next and solve for length n

Let me show you for length 5.

Suppose we pick a then we have a choice from

for length 4. Hence we have to solve the[a,e, i,o,u]subproblem with length 4now.if we didn’t pick a, then we have to choose from

[e, i,o,u] for length 5. Hence we have to solve the subproblem withlength 5 with 4 vowels now.

So adding up both will give us ways to create the required subarray.

Please try it your own to write up code, I know trying same also we will get doubt.

Code:

dp = [[0]*5 for i in range(0,n+1)] #creating Array

for i in range(0,5): dp[0][i] = 1

for i in range(0,n+1): dp[i][0] = 1

for i in range(1,n+1):

____for j in range(1,5):

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

return dp[n][4]