acash's blog

number of words with k max number of consecutive vowels
By acash, history, 4 years ago, In English

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.

I know its a dynamic programming problem but unable to figure out the recurrence.Please help!

word can contain letters only 21 consonants and 5 vowels

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I tried but not getting can you please help in finding the recurrence.I am new to DP

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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/25959

      And here is a general way for counting strings accepted by a DFA: https://web.cs.ucdavis.edu//classes/120/spring10/count.pdf

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply