Thanks! To clarify, It still fails with "set"? TBH, I was expecting something like this and it doesn't make sense to keep the TC this strict especially given other unoptimized solutions are passing.
Thanks. I learned string hashing from this video. Kinda frustrating that it TLEs though. I noticed the O(n^2) dp solution then just stared at the problem for ~30 minutes thinking how to optimize before giving up. Kind of strange that even the top contest participants confidently submitted O(n^2) trie solutions. It's like they collectively thought: "yeah this should pass per Leetcode standards" edit: jerryxu20 (7th place) got AC with a hashing solution. He sorted the lengths and added a break condition if i + lengths[j] >= n. He also used bottom-up dp
39:50 If you change
set word_lens to
unordered_set word_lens
It passes all testcases
Thanks!
To clarify, It still fails with "set"?
TBH, I was expecting something like this and it doesn't make sense to keep the TC this strict especially given other unoptimized solutions are passing.
Yes it fails using set I think it takes o(logn) time for insertion where in unordered set it takes o(1) time
Anyways nice solution
Favourite youtuber tbh
I was really hoping you would post it
Thanks!
This is next level explanation💥
Amazing explanations. Your channel is going to grow very big!
Waited for this video 💥
Thanks. I learned string hashing from this video. Kinda frustrating that it TLEs though. I noticed the O(n^2) dp solution then just stared at the problem for ~30 minutes thinking how to optimize before giving up. Kind of strange that even the top contest participants confidently submitted O(n^2) trie solutions. It's like they collectively thought: "yeah this should pass per Leetcode standards"
edit: jerryxu20 (7th place) got AC with a hashing solution. He sorted the lengths and added a break condition if i + lengths[j] >= n. He also used bottom-up dp
learned something new thanks mohan
LeetCode problem setters are probably high. In most of string hashing questions unoptimized solutions passes and optimized one times out
Great buddy
Thanks bhaiya. Was waiting for this video
You are awesome !! Just why i found your channel too late
Is it possible to find hashInRange by just dividing it by p powers without having to compute inversePpowers? Thank you.
You can't simply divide because the multiplication is already "mod M". Hence the number wouldn't be divisible if we use a normal division operator.
@@codingmohan is there any other way without having to find inversePpower? (Sorry if my question seems dumb)
Not really - because you are doing modular arithmetic.
If you want to divide you need to ferment little' theorem here.
726. Number of Atoms ,please explain this question
Your trie solution is not clear, can you explain a bit more on that?
your solution gave worng ans, it is giving me -1