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
@@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)
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 😊
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
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!
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!
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
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.
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
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
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.
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!
I'm a Java developer but your videos are the most helpful on CZcams when it comes to LeetCode problems. Do you think it's enough to understand and solve Blind 79 to pass a job interview?
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
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
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.
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
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
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.
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
#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
🚀 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!
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
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. :)
The legend has came back
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
Again the most simplest and amazing explanation ever on CZcams 👍🏻👍🏻😁😁
My very first hard problem 😂 . Thanks
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!
Such a complex problem, yet you make it so easy to understand! It almost seems obvious at the end!
Man ur amazing! I just saw the problem (Daily Challenge) and ur video popped up right after!
Got this question as my daily challenge literally 2 hours after you put up this video. Great timing.
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!
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
you make all the hard question look easy great job 👍
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.
the table is more than enough to understand the solution. tnks, as always, Happy Sunday!
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
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
I think a good idea for this channel would be to also engage with system design interview questions
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.
You explain comlpicated things in so simple and clear way 👍 Thank you!
Why dp problems are so complicated? :( Thanks for the video, happy and thankful you keep making new videos!
Timely video! Daily LeetCode Challenge
Thanks :)
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! 👍
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!
So long time I saw your vedio😉😉😉 but good time with you💓💓
As previous state is only required, the array is not necessary making it O(1) or constant space solution.
It was a long waiting
Your Leetcode tutorials are the best.
I'm a Java developer but your videos are the most helpful on CZcams when it comes to LeetCode problems. Do you think it's enough to understand and solve Blind 79 to pass a job interview?
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)
king is back
return of the lord of leetcode!
Congratulations 👏 for the 200k family 🥳😍
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
You have a very soothing voice.
Thanks!
Thanks a lot. You are really a good teacher.
Congrats on 200K
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 CZcams videos!
@@varunshrivastava2706 you could follow striver and geeksforgeeks CZcams channel. And neetcode is there on top of the list.
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);
}
}
King is back 👑
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
Neetcode staying prepped up for a senior position
When are you going to do Sys Design ?
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
Very clear explanation, as usual. Could you please tackle 1386. Cinema Seat Allocation? I would love to see your solution
This is next level
Such a beautiful combination problem
What a brilliant solution.
What was the reason for adding the mod function?
Dude ...
@4:50
Could you pls tell me about how you came about the reverse logic?
Can you do LC (721 I think) Merge Accounts? Or if you’ve already done one with similar structure, can you link?
can you try to get the grind 75 all into your videos!
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
Can you make a playlist using javscript as well?
Could you please make a video on cherry pickup problem(leetcode)
Wow welcome back!
Can someone pls explain the mod thing? I didn't get that.
Super Thanks
Missed you man
Boss is back!
Thank u!
Amazing
Missed your solutions
You can always mod result only, no need to mod each and every one
I think for some languages it would cause an overflow
what name of this ide ?
Do race car question leetcode 818
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.
Easiest hard question
Is it only me that makes me think he sounds like Colt Steele?
My brain is not for DP 😂
Can't you use a hash map Instead?
Yeah I think it also works
@@NeetCode for reducing memory consumption.
Hello
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
#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