Count Prefix and Suffix Pairs I & II - Leetcode 3042 & 3045 - Python

[@pouch6912]

my toxic trait is thinking "he doesnt mean me" when he says beginner

[@udaykiran2427]

Lol

[@arshadariff2430]

yo bro you are wild!

[@see7529]

Nah Id Understand

[@dazai-o3s]

I didn't understand ur comment at first but as I kept watching the video I realised exactly what u meant 😢

[@baetz2]

Hard problem wasn't so bad, you did a good job explaining the modification of a trie approach. It was actually easier to understand that some of the previous hard problems.

[@NeetCodeIO]

The hardest part is understanding Lee's solution

[@cse080chandrasekhar9]

@@NeetCodeIO kzbin.info/www/bejne/sILVpaaspJ2fna8si=kwbh5nX0bghb2uaD

[@ComfyWagie]

There's an even faster solution using rolling hashes instead of trie. It's 10 times faster in C++ and only use about 1/7 of the memory.

[@jahnaviyallamelli281]

The green with red shirt at start🤣

[@business_central]

totally 🤣🤣🤣🤣

[@satsub4083]

I loved the fact that the Trie explanation stuck with the Trie template from earlier problems which helped following along simple. Thank you

[@DNKF]

I have zero idea what you said in Lee's code at the beginning. After watching your explanation, I went back to your Lee's explanation. I could understand what you had said. So, your explanation and code are the key. Thanks bro! =]

[@business_central]

my favorite part today was when he was explaining and said : " you can imagine that a data structure like a prefix tree or a suffix tree is going to be useful and in fact you might think that probably we'll need both in this problem but actually it gets even more complicated than that" lol I like when you explain so well and also roast the problem xD

[@business_central]

Just finished it, and honestly your Trie solution is very nice, I did fully understand and it also helped me connect the dots I was missing when I myself tried a Trie solution. Big issue for me was that I was adding words and counting after causing me to always double count. Thank you so much for doing two problems at once, I think I've seen some crazier hard problem that I can't wait to see you take on. List of my hardest hards for anyone who want to try: 592. Fraction Addition and Subtraction (this one is medium) 2699. Modify Graph Edge Weights 432. All O`one Data Structure 2097. Valid Arrangement of Pairs

[@jayjw1]

Not sure why, but I love Tries. Thanks for the videos Papa Neet!

[@jimizuka-bk7ct]

I was using KMP to get all the possible prefixes that are also suffix and storing them in a hashmap. 593/596 passed and 3 failed because of memory limit exceeded. Then I tried to generate hash on those strings but was facing some conflicts there. This solution with trie is simply amazing. Thanks a lot.

[@firefouuu]

Once again the Rabin Karp/Rolling hash algo can really save your day here

[@moralized]

Rabin Karp doesn't work on part II because of a nasty test case: words = ["a", "aa", "aaa", "aaaa", etc.] which forces worst case time complexity on Rabin Karp, O(n^2)

[@ComfyWagie]

@@moralized Rolling hash was 10 times faster than Trie for me y = 127 * x[m] + x[n]; hash = (hash * 10007 + y) ^ 0xC0FFEE;

[@craziegeek]

​@@moralized Nope. You can use a hashmap to keep the count and still do in O(N*L).

[@pravargupta]

the way to do it was brilliant goddam

[@vaibhavgade8573]

Neat solution, not much hard to understand but definitely hard to come up with. I figured out that the time complexity is O(words.length * words[i].length) but how to calculate space complexity for this solution?

[@ahmedtremo]

that was great explanation with extra useful details

[@rimanagi2110]

Lee is a monster. Can't imagine how did he come up with his first line.

[@yashsrivastava3194]

Can you please make a video on this problem, 3409. Longest Subsequence With Decreasing Adjacent Difference

[@MP-ny3ep]

Thank you for the daily!

[@sauravsingh4497]

12:45 i was thinking of the same solution because when I hear prefix I try using a trie but then I saw ways to make a separate suffix tree I could not come up with a efficient way so just did brute force

[@coder4337]

Did a codesignal today with this question but only the prefix but I was baffled since I thought it was so easy but I kept getting time limit exceeded. Little did I know all ik is leetcode easies lol

[@alessandromaranelli6210]

Great solution! I think that solution is overcomplicated though. I just iterated through the words and inserted them in the trie, that is a dict. When a word ends, I used the special character '*' and instead of saying d['*'] = {}, I assigned it a counter. Then for each new word, if '*' is in the dict you can just check if words[i][-j-1:] == words[i][:j+1] . If yes, then update the final counter with d['*']

[@willzin-da-esfiha]

It can be easily explained if you show properties of the data structure used first. Every time that some key in the dict receives a sum of 1, it represents the end of a string w. If you find a number, it represents the number of times of some string is repeated in the string set. If you find a number, it means that at the point of the current string, you have found a preffix+suffix combination of a string that can be repeated in the string set. My only problem with this answer is if the input was ["a", "aba", "aca", "a"], It would return 3 or 5? And if the input was ["a", "a", "aba", "aca"], it would return 3 or 5? Maybe res could be increased in a second loop after dict annotation to solve this problem. Btw, nice video!

[@Atzee]

Hoo lee Lmao im still laughing Didnt evn noticed😂😂😂

[@andrewcenteno3462]

The warning at the beginning sent me rolling, 'it will break your spirit" lmfaaoooo. I've been there, at 600+ let's hope im ready

[@jamestwosheep]

Using two characters as the trie key is so brilliantly clever! I was struggling for a long time trying to figure out a 2 trie structure approach, but that method was always leading me to a O(n^2) runtime.

[@dongtandung9671]

That "Hoo Lee ****" was unexpected!

[@business_central]

Btw Lee's solution is even 10x more concise than the editorial lol. Is it same time complexity ?

[@guruprasath2862]

11:10 hope everybody is human?

[@juanmacias5922]

8:13 Ho Lee Pho ;D

[@anand8412]

for input: ["a","aba","ababa","aa"] first loop("aa"): (a,a) - 1 res is 1-1 = 0 second loop:("ababa") (a,a) -2 (b,b) - 1 (a,a) - 1 (b,b)-1 (a,a) -1 res is 1-1 = 0 third loop("aba"): (a,a) - 3 (bb) -2 (a,a) -2 res is 2-1=1. ("aba", "ababa") fourth loop("a"): (a,a) - 4 res is 4-1=3 ("a", "aba"), ("a", "ababa") ,("a", "aa") So answer is 1+3=4

[@_withoutwax]

LOL the warning at the beginning

[@magicall9596]

I managed to get accepted the hard version of problem on leetcode, but not because I wrote good code or anything, I think it's because their tests are not that good. So essentially what I did, is as I iterated through the list of words, I was adding previous ones to the hash table, where the each word was the key, and the amount of time it was encountered was value and then I iterated through the hash map instead of iterating through list extra times. It works better only if every single word is the same, so hash map stays pretty small, but in the worst case scenario if every single word is different it's not better at all and still O(n^2). But it still passes on leetcode. Here's my code in python: class Solution: def countPrefixSuffixPairs(self, words: List[str]) -> int: count = 0 seen = {} for word in words: for candidate in seen: if word[:len(candidate)] == word[len(word) - len(candidate):] == candidate: count += seen[candidate] seen[word] = seen.get(word, 0) + 1 return count

[@codewithven9391]

Well, tmr is gonna be a hard problem

[@Reck1025]

I couldn't stop laughing every time I heard walrus operator 😂😂

[@unlucky-777]

10:48 Hey neetcode, how did you do that?

[@sumitkumarmahto5081]

ctrl + / in windows to comment or uncomment a block of code

[@MrPhoenix-007]

ctrl + ? in windows

[@ramennudeln247]

I laughed pretty hard at the no pun intended comment haha.

[@mohammadazhari9527]

Can you try a live stream doing leetcode contest .. i think it will be fun to watch

[@NeetCodeIO]

It's not allowed to stream contests

[@nileshbhanot2776]

Can anyone please the part, why are we incrementing the cur.count variable?

[@NeetCodeIO]

to count the number of times a char has been inserted with a given prefix/suffix. remember we are trying to count the pairs

[@sachinsudheer]

300 problems in and nowhere close to being able to solve this on my own. how, just how ?

[@pastori2672]

DOUBLE SHIRT

[@ngneerin]

Here is the simplest version of the trie solution def countPrefixSuffixPairs(self, words): trie = { "count": 0 } ans = 0 for word in words[::-1]: curr = trie for i in range(len(word)): pair = word[i] + word[len(word)-i-1] if pair not in curr: curr[pair] = { "count": 0 } curr = curr[pair] curr["count"] += 1 ans += curr["count"] - 1 return ans

[@AnandaKrishna-t3h]

Skipping 2nd part😊

[@floatingpoint7629]

the count part was confusing other then that i got the gist of it

[@nechiii-2863]

I realised i'm --human; now

[@prajwals8203]

hmmm...strange, the time you submitted double trie solution there were no previous submission of brute force approach but the time stamp clearly indicates you definitely submitted after brute force do was it another account?

[@NeetCodeIO]

They are different problems, I submitted brute force on the other one

[@prajwals8203]

​@@NeetCodeIO Ahh I feel so embarassed now...I thought I found some top secret....

[@herambsharma5879]

green and red shirt🤣🤣🤣🤣

[@deepanshuverma6237]

💀💀

[@ngneerin]

it is not as hard for your viewers to understand as you are assuming it is