Count Vowels Permutation - Dynamic Programming - Leetcode 1220 - Python
Вставка
- Опубліковано 8 чер 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/count-v...
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. - Наука та технологія
🚀 neetcode.io/ - The best FREE site to prepare for Coding Interviews
🥷 Discord: discord.gg/ddjKRXPqtk
🐦 Twitter: twitter.com/neetcode1
Thanks you sir..
Hey can you please make video on leetcofe 395 : longest substring with atleast k repeating characters , and show both approaches, Divide and conquer as well as sliding window
The return of the king.
The drawings + the way you mapped the ending letters to an index made this problem really easy to understand
Glad it was helpful!
@@NeetCode You're providing us with so much value. Thanks for providing us with these high level concepts. I'm in my second year of college and the resources you're providing give me a ton of hope for the future in terms of understanding these concepts
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)
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)
Man. The solution works. Awesome!
The legend has came back
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. :)
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
you make all the hard question look easy great job 👍
Again the most simplest and amazing explanation ever on UA-cam 👍🏻👍🏻😁😁
My very first hard problem 😂 . Thanks
Got this question as my daily challenge literally 2 hours after you put up this video. Great timing.
Man ur amazing! I just saw the problem (Daily Challenge) and ur video popped up right after!
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!
the table is more than enough to understand the solution. tnks, as always, Happy Sunday!
Timely video! Daily LeetCode Challenge
Thanks :)
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 😊
GS?
@@Terracraft321 goldman
You explain comlpicated things in so simple and clear way 👍 Thank you!
Your Leetcode tutorials are the best.
Such a complex problem, yet you make it so easy to understand! It almost seems obvious at the end!
Thanks a lot. You are really a good teacher.
Congratulations 👏 for the 200k family 🥳😍
Thank you so much! Well explained. I recommended your channel to my friends. Plus you inspire me a lot. Even though I work for a great company, and our product is used by millions, we have customers such as Google, Apple, etc, I still dream about becoming a Googler.
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
Congrats on 200K
You have a very soothing voice.
return of the lord of leetcode!
So long time I saw your vedio😉😉😉 but good time with you💓💓
King is back 👑
Wow welcome back!
I think a good idea for this channel would be to also engage with system design interview questions
Thanks!
Such a beautiful combination problem
What a brilliant solution.
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
It was a long waiting
My idea is to do dfs with caching. Yours is to think backward and cnt the number of str end with certain letter and make the dp arr much easier to understand! Love it!
king is back
As always, Thank you for the great explanation.
I was actually thinking to work on my understanding for these ending char dp questions . Nice that leetcode chose this question for today's daily challenge , and you chose to upload a video for this.
I am thinking about starting to learn dynamic programming. Any resources that you can suggest me?
@@varunshrivastava2706 just start with leetcode easy dp questions.
@@uditsharma5688 By resources I meant UA-cam videos!
@@varunshrivastava2706 you could follow striver and geeksforgeeks UA-cam channel. And neetcode is there on top of the list.
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.
Why dp problems are so complicated? :( Thanks for the video, happy and thankful you keep making new videos!
This is next level
Thank u!
Missed you man
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
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
Brilliant.
That's what had me stumped why it was failing when testing n = 144.
Was expecting 18208803, but instead was getting totally wrong result, while other tests passed.
Thank you!
I'm a Java developer but your videos are the most helpful on UA-cam when it comes to LeetCode problems. Do you think it's enough to understand and solve Blind 79 to pass a job interview?
Thanks much and please stay free! I've never sent a gift to an online but you deserve it (feel special:) )
Super Thanks
Boss is back!
Amazing
Can be memory efficient if used only two rows in dp where updating 2nd row using 1st row and making both rows equal at end of each iteration
Yep, exactly! 👍
Very clear explanation, as usual. Could you please tackle 1386. Cinema Seat Allocation? I would love to see your solution
Dude ...
@4:50
Could you pls tell me about how you came about the reverse logic?
As previous state is only required, the array is not necessary making it O(1) or constant space solution.
Can you make a playlist using javscript as well?
Can you do LC (721 I think) Merge Accounts? Or if you’ve already done one with similar structure, can you link?
Ok real question, after working at google for sometimes now, have you actually use any of the hard/tricky data structure & algorithms in job?
Absolutely not
What was the reason for adding the mod function?
thank you for this vide. could you please make the " 419 - battleship in a board " problem. You're the only one I understand his explanation. Thank you a lot for this valuable channel
I used dfs and @cache.It actually works ,I don't know if it's appropriate sometimes to solve dp problem like this?
Yeah that also works!
how did you do it?did you just cache the count for each ith char in the string together with the last char?
@@memeproductions4182 here is a recursive solution in java
class Solution {
Map map;
int mod;
Map cache;
public int countVowelPermutation(int n) {
mod = 1000000000 + 7;
cache = new HashMap();
map = new HashMap();
map.put('a', Arrays.asList('e'));
map.put('e', Arrays.asList('a', 'i'));
map.put('i', Arrays.asList('a', 'e', 'o', 'u'));
map.put('o', Arrays.asList('i', 'u'));
map.put('u', Arrays.asList('a'));
int count = 0;
for(char c: map.keySet()){
count = (count + count(n - 1, c)) % mod;
}
return count;
}
private int count(int n, char c){
if (n == 0) return 1;
String key = n + "" + c;
if (cache.containsKey(key))
return cache.get(key);
int count = 0;
for(char nc: map.get(c)){
count = (count + count(n - 1, nc)) % mod;
}
cache.put(key, count);
return cache.get(key);
}
}
Could you please make a video on cherry pickup problem(leetcode)
Using hash maps would make the time complexity better, because insert operation is O(1) in hash maps whereas in list the insert operation is O(n)
Missed your solutions
NEET IS BACK AT IT AGAIN WITH A BANGER SOLUTION. NEET FOR PRESIDENT!!! Waiting for the day for Sundar to retire from Google and we get NEET as CEO. Until that day, I will continue to comment subscribe like share his videos until Sundar forcefully retires and gives his seat to Neet
Can someone pls explain the mod thing? I didn't get that.
can you try to get the grind 75 all into your videos!
Neetcode staying prepped up for a senior position
When are you going to do Sys Design ?
what name of this ide ?
Same solution with exponentially lower space complexity
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) % 1000000007
Nice! Best part of python is not having to worry about overflow
I find that an issue while preparing for interview. Interviewer could be from java background and would be expecting solution to include methods to avoid overflowing
Do race car question leetcode 818
You can always mod result only, no need to mod each and every one
I think for some languages it would cause an overflow
Easiest hard question
Can't you use a hash map Instead?
Yeah I think it also works
@@NeetCode for reducing memory consumption.
My brain is not for DP 😂
can someone give the c++ code
int countVowelPermutation(int n) {
if(n==1) return 5;
if(n==2) return 10;
long a=1,e=1,i=1,o=1,u=1,mod=1e9+7;
long a2,e2,i2,o2,u2;
for(int j=2;j
Yeah, you can write it this way:
#define NO_CHARS 5
#define MOD 1'000'000'007
#define ll long long
class Solution {
public:
int countVowelPermutation(int n) {
ll dp[n+1][NO_CHARS];
// base case
for (int j = 0; j < NO_CHARS; ++j) dp[1][j] = 1;
int a = 0, e = 1, i = 2, o = 3, u = 4;
for (int j = 2; j
Is it only me that makes me think he sounds like Colt Steele?
Hello
Hi neetcode, just saw you website. I think I am the first to saw the changes. Can you give some discount to your Indian user Rs10000($129) is a lot. Can you make it Rs 5000. I will buy it in a giffy.
#I think this is o(1) solution
class Solution:
def countVowelPermutation(self, n: int) -> int:
a, e, i, o, u = 1, 1, 1, 1, 1
for _ in range(2, n + 1):
a, e, i, o, u = e + i + u, a + i, e + o, i, i + o
return (a + e + i + o + u) % 1000000007
I quit being a software engineer
Why??
It’s to hard and it got boring
If you don'tt enjoy coding, then it'll be definitely boring