Leetcode diary: 1641. Count Sorted Vowel Strings [DP problem]
Tags: javascript, algorithms, devjournal, motivation
Published: 2022-01-09 09:56:03

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.  

This problem is HARD; I am newbie to DP still.

Looking at the problem, I knew that I could use a technique that I used before: [abstracting strings into ints for easier manipulation](https://dev.to/kevin074/leetcode-diary-890-find-and-replace-pattern-561b). 
This is just so I don't have to loop to check where a letter is in the array(or string) index each time. 
[although I JUST realize you could just check for like "a" > "e", oh well].

The next thing I realized is that technically I don't need to store all the permutations, I just need to count how many leafs in the end of the tree-like branching out there are (or you can revisualizes as how many last iteration at the end of DFS/BFS/recursion you use).

so there is the first version code:

```
var countVowelStrings = function(n) {
    let answers = 0;
    
    function recur (n, index) {
        if(n === 0) { 
            answers++; 
            return;
        }
    
        for (let i = index; i < 5; i++) {
            recur(n-1, i);
        }
    }
    
    recur(n, 0);
    return answers; 
};
```

This works, but this isn't really a DP solution.
So to work on a proper DP solution, I'd need to get the permutations so that there is something to remember for:

```
var countVowelStrings = function(n) {
    const answers = [];
    function recur (n, currentNum) {
        if(n === 0) { 
            answers.push(currentNum); 
            return;
        }
    
        for (let i = 5; i > 0; i--) {
            if(currentNum !== 0 && currentNum % 10 < i) { continue; }
            
            const value = currentNum * 10 + i;
            recur(n-1, value);
        }
    }
    
    recur(n, 0);
    return answers.length; 
};
```

This would get me the permutations, but it won't pass the submission cause the array grew too large.
However, I thought it's best to work out an actual DP solution first so:

```
const memo=[[0]] //[0] is necessary;
var countVowelStrings = function(n) {
    if(n === 0) return 0;
    if(memo[n]) { return memo[n].length }
    
    const answers = [];
    function recur (n, currentNum) {
        if(n === 0) { 
            answers.push(currentNum); 
            return;
        }
    
        for (let i = 5; i > 0; i--) {
            if(currentNum !== 0 && currentNum % 10 < i) { continue; }
            
            const value = currentNum * 10 + i;
            recur(n-1, value);
        }
    }
    
    recur(n, 0);
    memo[n] = answers;
    return answers.length; 
};
```

But dang dude, there ain't no way I'd pass submission with like a million int permutations. So I needed someway to reduce the memory load. Fortunately for me, I figured out that I don't need the whole number representation like 55555, I just needed 5! This is because it's only the single digit number that mattered, as evidently by "currentNum % 10". Therefore I only need to store the values as 5:

```
const memo=[[0]] //[0] is necessary;
var countVowelStrings = function(n) {
    if(n==0) return 0;
    if(memo[n]) { return memo[n].length }
        
    n -= (memo.length-1);
    let currentArray; 
    while (n--) {
        const newArray = [];
        currentArray = memo[memo.length-1];
        currentArray.forEach(function(currentNum){            
            for (let i=5; i>0; i--) {
                if(currentNum !== 0 && currentNum < i) { continue; }
                newArray.push(i);
            };
        });
        
        memo.push(newArray);
    }
    
    return memo[memo.length-1].length; 
};
```
At this point I realized it's hard to understand the problem via recursion. Since we are already storing the whole array of previous calculations, I just needed to recall whichever the latest calculation is, this is the essence of DP! So I am back to my favorite while loop pattern and iterate on each element instead. Technically I could continue with a recursion, but it just is not intuitive enough and my head was spinning already. 

This passed with really good performance, asides from some weird solutions like [this](https://leetcode.com/problems/count-sorted-vowel-strings/discuss/1672474/Javascript-O(n)-dynamic-programming-detail-explanation).

This is also probably the best DP solution without using math or notice some weird patterns (Although honestly worthwhile to bang your brains out for). The drawback is that I use a lot more space than other solutions, but mine is also way faster than other minimal-space-no-math solutions (mine is 2 - 3X fastest and others are 4-7X). 

I'll take this small victory today. 

Let me know anything on your mind after reading through this, THANKS!