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;
}