Count Vowels Permutation - Dynamic Programming - Leetcode 1220 - Python

0:00 - Read the problem
1:20 - Drawing Explanation
8:02 - Coding Explanation

leetcode 1220

#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[QazJer]

The drawings + the way you mapped the ending letters to an index made this problem really easy to understand

[sirmidor]

Since in each step we only need to "look back" at the results of the previous iteration and no further back, you can do this with just one array, as long as you use unpacking (multiple temp variables are possible too) so that newly calculated values do not interfere with calculating other new values:
arr = [1, 1, 1, 1, 1]

for _ in range(n - 1):
arr[0], arr[1], arr[2], arr[3], arr[4] = (
arr[1],
arr[0] + arr[2],
arr[0] + arr[1] + arr[3] + arr[4],
arr[2] + arr[4],
arr[0]
)

return sum(arr) % ((10 ** 9) + 7)

[habashyjr]

The O(1) memory solution:

def countVowelPermutation(self, n: int) -> int:
a, e, i, o, u = 1, 1, 1, 1, 1
for _ in range(n - 1):
a, e, i, o, u = e + i + u, a + i, e + o, i, i + o
return (a + e + i + o + u) % (10**9 + 7)

[charziken]

Hi, thanks a lot for these videos! I remember how I used to be terrified of leetcode (still am a bit haha) but your approach and thought process in these videos have rubbed off on me and massively improved my confidence during my job search. I’ve now got an offer from GS 😊

[arpanbanerjee]

When I see that you have put up a video explaining any problem, I am so sure that I will understand it. This peace of mind we get. :)

[akshitdayal]

You're the best Neetcode!!!! Everytime I search for a leetcode question on youtube and I see that Neetcode has a video on it, I'm the happiest person coz your explanation is the besttt!!! Thank you so much for everything that you do

[mohithadiyal]

Again the most simplest and amazing explanation ever on YouTube 👍🏻👍🏻😁😁

[doublegdog]

Neetcode the best code. Landed a job at amazon thanks to grinding supplemented with your videos but I still like watching your solutions even though I dont need them anymore haha. Keep up the great work!

[awepossum]

Such a complex problem, yet you make it so easy to understand! It almost seems obvious at the end!

[darkjemdude]

Got this question as my daily challenge literally 2 hours after you put up this video. Great timing.

[sugandhm]

Java coders in line 16 of this code make sure u mod two times to avoid overflow and incorrect answers.
We have to put mod after addition of every two terms and adjust brackets accordingly.

dp[j][a] = ( (dp[j-1][e] + dp[j-1][i]) % mod + dp[j-1][u] ) % mod

[kyriakoskourkoulis]

Man ur amazing! I just saw the problem (Daily Challenge) and ur video popped up right after!

[pironobcoding]

you make all the hard question look easy great job 👍

[estifanosbireda]

the table is more than enough to understand the solution. tnks, as always, Happy Sunday!

[lopotun]

You explain comlpicated things in so simple and clear way 👍 Thank you!

[simonlitvinskii]

Since all formulas are linear, you can rewrite step as matrix multiplication and then use fast exponentiation to reach O(log n) solution, and it still would be O(1) memory

[CostaKazistov]

Timely video! Daily LeetCode Challenge
Thanks :)

[jlpeng]

your explain is so good. everytime i watch your video i feel i can beat all hard leetcode questions and get to google offer. but everytime i actually do the hard question on leetcode, i still struggle. haha

[infinitygod]

Just until a week ago i didn't even know practical dynamic programming. Watched few vids and now I came up with an ans in a minute after pausing you vid at 1:16 and now i have to see if my ans is correct before checking out entire video

[lawrencejustin]

Thanks alot Neet! It appears you have mixed o for u. O can be followed by i and u while u is followed by i. Also, when the question says n7mber of strings that could be formed by n length, how does your n=2 example fit in? I was thinking each of the characters can only form strings of length n only that the condition holds. In your example, I didn5 see the relationship between the 5 characters and n.