acash's blog

By acash, history, 5 weeks ago, ,

Given a word length n and max number of consecutive vowels k ,we need to tell how many words that we can form using given constraints.

n=3 and k=2 means we have to tell the number of words of length 3 and in which we can use at most k consecutive vowels.

word can contain letters only 21 consonants and 5 vowels

• -4

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by acash (previous revision, new revision, compare).
 » 5 weeks ago, # |   +3 Define $dp_{i, j}$ equal to number of words of length $i$ such that no $k$ consecutive letters are vowel and $j$ last letters are vowel, you should be able to fill this on your own.
•  » » 5 weeks ago, # ^ |   -8 I tried but not getting can you please help in finding the recurrence.I am new to DP
•  » » » 5 weeks ago, # ^ |   0 Here is an almost identical problem and the first answer is very understandable (but instead of solving the recurrence you would use DP) https://math.stackexchange.com/q/2023212/25959And here is a general way for counting strings accepted by a DFA: https://web.cs.ucdavis.edu//classes/120/spring10/count.pdf
•  » » » 5 weeks ago, # ^ |   0 I think DeadlyCritic gave you a good reply. How do you find $dp_{i,j}$? This is an answer for the words of length $i$, such that exactly last $j$ letters are vowels (and $j$ must not exceed $k$, otherwise $dp_{i,j} = 0$).Obviously, if $j > i$, $dp_{i,j} = 0$ (there can't be more letters in the word than its length).If $j = i$, it is just the number of words of length $i$, all consisting from vowels ($5^i$).For $j < i$, you try to understand, how many words of length $i$ with last $j$ letters being vowels exist, knowing the number of all words of length $i - 1$. If you append a consonant ($j = 0$) to the word of length $i-1$, then any of $dp_{i-1,j}$ words will work (so $dp_{i,0}$ is their sum). If you append a vowel ($j \ne 0$), then any of $dp_{i-1,j}$ words will work, apart from $j = k$ (because you add one vowel, so there cannot be already k vowels in the end of the $i-1$-word).