This is the beauty when someone red on codeforces solves interview problems. It was so easy for you Errichto, but for the sake of your audience you explained it thoroughly. Thanks :)
Great stuff, Errichto! There are far more successful TH-camrs with a greater following. BUT I think you're way ahead of them in terms of material and quality content. Would love to see more videos like this. I think at the moment you're far under rated. Keep up the good work! 😀
As Errichto pointed out, using a palindrome, we can have a sub palindrome by removing two outermost value. The sub palindrome has the same parity as the original palindrome (the longer one). It's a fact that a palindrome with EVEN length can only have sub palindromes with EVEN length. The same thing happens to palindromes with ODD length - their sub palindromes must have ODD length too. Therefore, if we found a palindrome which has an EVEN length, the possible longer palindrome derived from it must have an EVEN length too (i.e they have the SAME parity). The parity part of Enrichto algorithm is to make sure we only looking for length that are worth checking. E.g. If we want to check if there's a palidrome with EVEN length, we will only look for EVEN length cases. The binary search really helps this idea to happen in O(logN); but we can implement it in O(N) just by looping through the string with the index increase by 2 each loop Hope this helps
@@huan8036 Can you explain a bit more of how binary search is even used here? I understand the even and odd length logic of the palindrome. But how and why Binary search is used in this is still not clear
Notice that any palindromic substring is a common substring of s and rev(s). Now look at suffix structures in context of finding longest common substring.
Could someone kindly refer me to some material explaining the use of parity in Binary search? I did not exactly understand what @Errichto was trying to do there.
This optimization isn't strict to c++. When we use &, it'll compute the 2 parts of operations independently of your logical value, when we use &&, it'll check the first part and if it's false the second part will not be computed because it'll be false anyway. The same works with || and |, when we use ||, if the first part is true, the second will not be computed because the operation will be true anyway.
@@a.yashwanth Yes it works in Java since I kept the length check before the string check and my solution got accepted albeit with long runtime. Just one little manoeuvre to change the verdict from TLE to Accepted.
lol i come after struggling like hell: "quite an easy problem" me: ded. "...if you have competitive programming experience", me: oh phew, nope just a job that has nothing to do with LC.
on average how many problems you solve in a day (now and in the past). and Do you recommend sticking to a problem even when you cant get you head around it for days or leave it and look at the solution(or hint).
Hi Errichto thank you for the video! I really appreciate your explanation on the problem that many users struggle. Do you mind if you could make more videos on the solution that are on the list from top 100 liked questions or top 100 interview questions that are more of a medium level from the LeetCode? this way I think more entry-medium level coders can enjoy your channel more instead of diving into your explanation on hard algorithmic questions (though I enjoy those too). Hope you can take this into a consideration! thank you always.
Why this two loops (odd/even length) are one after another? Why aren't they used based on length of string? Why it doesn't break when break when used on odd length string? (because in this case part of algorithm for odd is used first, and then part for even length is used on odd length) Why isn't it a problem? edit: Also why after using only one loop (for even or odd) this is not working properly? edit2: Ok, now I (probably) understand. One loop is for finding odd length palindrome (not odd length input), and other is for even length palindrome (not even length input). Am I right now?
@@devendrasingh4776 normally you search for a value in array or something but in this he was trying different answers in binary search way, it was long ago so i dont remember much.
Love this! Because this is a simpler problem (comparing others in this channel) I could understand the proccess and I've got so many things to learn. Thank you!
Can you please give us tutorial on Manacher's Algorithm !! i didn't understand well i have seen lots of video on Manacher's Algo!! you teaches very well!!
Personal opinion but I would always go O(nlogn) with hashing and binary search. Its more intuitive than manacher algorithm and has just a logn extra factor.
Because maybe there is a palindrome of length 6 but not of length 5. So what happens if you ask "can answer be 5?" in binary search and it turns out it can't? You will now search for answer between 1 and 4.
@@Errichto thank you for replying, I understood it completely wrongly previously so I was very confused. But now I completely understand the solution.. :D This is very helpful btw!
@@Errichto same level, also tips on data structures/algo if possible. You know like how to approach the problems with specific ds. Thanks for the reply.
Loved it, good job. One small observation, the string "aaaaaa....aaaaa" is a degenerate case for time in your algorithm. Instead of iterating mid in 0, 1, 2, 3, 4, 5..... you could iterate mid in n/2, n/2 + 1, n/2 - 1, n/2 + 2, n/2 - 2, .... Then just check if mid is far enough away from the edges to make a possible new best. That puts you really close to O(n) .
Sure, but then there can for sure be something similar to aaa...aa that will still be slower. It just shows that a problem author has a hard job of creating good tests :D
Goto any coding platform I prefer leetcode, select the difficulty to easy initially. First and foremost, make a habit of solving problem by thinking out loud, marker and board or pen and paper, DO use it, I repeat, USE MARKER AND BOARD OR PAPER AND PEN BEFORE EVEN LAYING YOUR HANDS ON THE KEYBOARD. Work our the problem slowly. This is the key. I used to jump straight to keyboard when I started doing competitive coding. Using the pen and paper beforehand to workout the problems (the process) builds problem solving networks in your head. Good luck! Don't give up!!
@@mahesh4274 I'd be super glad if I could help others, also, as you progress further you will realize that there are different domains of problems, like graph problems, string related problems, array, tree or hash etc. try to find the out which part is your weakest work on it. fight onn!!
Look at the Getting Started section in his github repo. If you want a good book download competitive programmer's handbook and practise codeforces, USACO, ACM problems, if youre prepping for olympiads, if for an interview, do some leetcode too.
My first thought was hashing. It's possible to hash the string and hash the reversed string. Then to find the longest palindrome, we can for every mid point (or double mid points for even length palindromes) iterate over it's prefixes and suffixes and compare them using hashes. Now add binary search and we don't have to do that for every pref/suf length and just for O(logn) of them. If I am not mistaken the total complexity would be O(n*logn)
You are completely right, and we can even get O(N) with hashes if we increment the answer by 1 instead of binary searching :) I just didn't want to talk about hashes in this video, too many things for a beginner's problem.
"we can for every mid point (or double mid points for even length palindromes) iterate over it's prefixes and suffixes and compare them using hashes." I don't understand this sentence. What do you mean by "it's prefixes"? By "it" do you mean "mid point"? If so, then what do you mean by a "prefix/suffix of a mid point"?
@@Errichto Can you please explain O(N) approach using hashes or can you give some reference to any blog or article where it is discussed ? I can only figure out O(NLogN) approach using hashes :(
Funny thing: if you implement this solution in Swift language, it won't be accepted due to exceeded time. Test case has 1000 "a" chars string. I guess the only option is to go with a suffix tree then.
Sir thanku so much for your videos ,sir I have completed the basics and now when I try to solve medium level question at codechef I get stuck maximum times only 1-2 questions per day can be solved.. This is my hackerank profile : www.hackerrank.com/profile/samarLove could you please tell me what I should I do next . I am not progressing now as fast I should be...
I got the first for-loop...it takes every element and expands towards the right and left side to get the largest palindrome...but can anyone explain the purpose of the second for loop?.
I'm doing this problem for the last 20 mins, and it seems that the test case no 26('abb') is giving me the wrong result. When I checked it by inputting the input in the test case, it's giving me the correct answer. Anyone can explain to me why is it happening?
thank you for the lovely 25 minute explanation even though i know you can do this in 25 seconds. you are truly a gift to us all who enjoy competitive programming. p.s. i finally solved my first problem solved in under 5 minutes during a 3-problem online assessment, and boy did it feel amazing! Too bad the other two took about an hour each because i got ahead of myself after the first solution :P
The high is amazing when you solve a (relative difficult ) problem. The low is terrible when you trying to understand a solution or freeze in interview.
Can anyone tell in the binary search method why we change the low and high value if it is not match with parity and we also increase the mid value if it is not match with parity instead of that can we only modify the mid value if it is not match with the parity.. Please correct me if i am wrong.
Hi @Errichto, I'm wondering how making change to parameter type: (string s) -> (const string& s) would let a for loop exit with early condition hence faster-than-linear runtime. @5:58. Do you mean such change is coming from the algorithmic change and changing the paramter type would only save CPU from using extra memory to take in s? or is there something special about how for loop treats a reference ? Thanks for your time in advance
love ur videos bro, didnt quite understand in binary search part tho, maybe with a little bit more replay i can understand it, thank you for the video!
Hello Errichto...Kindly upload videos on greedy strategy...I have solved more than 100 Div2C problems...yet whenever a greedy comes even in B ,I cant figure out whether greedy will work or not...or to which variable I should do greedy on.
Thanks for the explanation. I came to watch your video after I solved the problem myself. I was not disappointed because you explored many options. For N^2 time complexity what I did was reversed the original string and used longest common substring between the original string and the reversed string. I got an edge case where it was finding strings of length 2 to be palindrome even if they were not.
![[UNCUT] “บอสณวัฒน์” ลากไส้!! ใครหนุนหลัง "แม่ตั๊ก ป๋าเบียร์" I คนดังนั่งเคลียร์ I 30 ก.ย. 67](http://i.ytimg.com/vi/QlD7mU2KKRk/mqdefault.jpg)
Your first statement made me crying for 2 hours straight
lmao
It broke my heart
🥲
Same!
crying since 2 years straight
true
I love your tutorials, how you go from the naive solution to the optimized one
Thanks :)
I too liked his same approach, it helps the people who don't have the ability to see optimized solutions at the very beginning.
@@Errichto Given an array of integers,find the maximum value of a[i] - a[j] + a[k] with constraints I
@@aj9706 hi will seeing it as maximise ak-aj+ai and transversing i with j= i+1 and k=n-1 work?
This is the beauty when someone red on codeforces solves interview problems. It was so easy for you Errichto, but for the sake of your audience you explained it thoroughly. Thanks :)
errichto makes me wanna leave programming and love programming at a same time..
I wish you covered the Manacher's algorithm as well.
yes!
Great stuff, Errichto! There are far more successful TH-camrs with a greater following. BUT I think you're way ahead of them in terms of material and quality content. Would love to see more videos like this. I think at the moment you're far under rated. Keep up the good work! 😀
I didn't understand the parity part, can anybody elaborate on that ?
As Errichto pointed out, using a palindrome, we can have a sub palindrome by removing two outermost value. The sub palindrome has the same parity as the original palindrome (the longer one).
It's a fact that a palindrome with EVEN length can only have sub palindromes with EVEN length. The same thing happens to palindromes with ODD length - their sub palindromes must have ODD length too.
Therefore, if we found a palindrome which has an EVEN length, the possible longer palindrome derived from it must have an EVEN length too (i.e they have the SAME parity).
The parity part of Enrichto algorithm is to make sure we only looking for length that are worth checking. E.g. If we want to check if there's a palidrome with EVEN length, we will only look for EVEN length cases.
The binary search really helps this idea to happen in O(logN); but we can implement it in O(N) just by looping through the string with the index increase by 2 each loop
Hope this helps
parity is for checking the length of best_s is whether odd or even
@@huan8036 Can you explain a bit more of how binary search is even used here? I understand the even and odd length logic of the palindrome. But how and why Binary search is used in this is still not clear
I just love how you go from the simplest to the most optimized solution and the way you explain the process for optimizing the code.
I'd love to watch O(n) solution from you, great video btw
Yes indeed.
Notice that any palindromic substring is a common substring of s and rev(s). Now look at suffix structures in context of finding longest common substring.
Could someone kindly refer me to some material explaining the use of parity in Binary search? I did not exactly understand what @Errichto was trying to do there.
yeah ..me too
The small c++ optimizations you mentioned in this video will be really helpful for me while coding. Thanks for putting out content like these
This optimization isn't strict to c++. When we use &, it'll compute the 2 parts of operations independently of your logical value, when we use &&, it'll check the first part and if it's false the second part will not be computed because it'll be false anyway. The same works with || and |, when we use ||, if the first part is true, the second will not be computed because the operation will be true anyway.
@@deDeca1000 But this doesn't work in java.
@@a.yashwanth I guess it works too as a simple research that I did here.
@@a.yashwanth Yes it works in Java since I kept the length check before the string check and my solution got accepted albeit with long runtime. Just one little manoeuvre to change the verdict from TLE to Accepted.
Not able to understand the second solution in which you use the parity can you explain it with some diagrams. Thanks for sush easy explanations.
lol i come after struggling like hell: "quite an easy problem" me: ded. "...if you have competitive programming experience", me: oh phew, nope just a job that has nothing to do with LC.
on average how many problems you solve in a day (now and in the past).
and
Do you recommend sticking to a problem even when you cant get you head around it for days or leave it and look at the solution(or hint).
ive just replied to get notification for answer
@@davidalexandru7848 welcome
Hi Errichto thank you for the video! I really appreciate your explanation on the problem that many users struggle. Do you mind if you could make more videos on the solution that are on the list from top 100 liked questions or top 100 interview questions that are more of a medium level from the LeetCode? this way I think more entry-medium level coders can enjoy your channel more instead of diving into your explanation on hard algorithmic questions (though I enjoy those too). Hope you can take this into a consideration! thank you always.
watching you makes me think of quitting my job
Why this two loops (odd/even length) are one after another? Why aren't they used based on length of string? Why it doesn't break when break when used on odd length string? (because in this case part of algorithm for odd is used first, and then part for even length is used on odd length) Why isn't it a problem?
edit: Also why after using only one loop (for even or odd) this is not working properly?
edit2: Ok, now I (probably) understand. One loop is for finding odd length palindrome (not odd length input), and other is for even length palindrome (not even length input). Am I right now?
you really made me question my understanding of binary search.I didn't get that n^2logn approach.
Edit: i get it now , thanks.
Tell me bro what you understand please . 😢😢
@@devendrasingh4776 normally you search for a value in array or something but in this he was trying different answers in binary search way, it was long ago so i dont remember much.
@@Laeyz but why he did even odd thing
Love this! Because this is a simpler problem (comparing others in this channel) I could understand the proccess and I've got so many things to learn. Thank you!
Can you please give us tutorial on Manacher's Algorithm !! i didn't understand well i have seen lots of video on Manacher's Algo!! you teaches very well!!
Personal opinion but I would always go O(nlogn) with hashing and binary search. Its more intuitive than manacher algorithm and has just a logn extra factor.
This is so informative and awesome!
Thank you :)
Wow, no ads in any video.... This man is a legend
Thank you brother from another mother, everyone on TH-cam showing the code of optimised approach,
Only you showed the brute force
helpful details, that was amazing
Thank you so much for these Leetcode tutorials. Absoultely love them !
Mindblowing sir .
Thankyou very much .
Your way of explaination is unique.
Your explanations of problems are awesome going from bruteforce approach to optimisation......
Can you please make a video on Manacher's Algorithm Errichto?
I still didn't understand parity and binary search based solution to this problem. Any good materials for this to read & analyse?
06:08 why does comparing by reference is faster than comparing two string variables?
I don't understand the binary search one. Why do we need to consider parity?
Because maybe there is a palindrome of length 6 but not of length 5. So what happens if you ask "can answer be 5?" in binary search and it turns out it can't? You will now search for answer between 1 and 4.
@@Errichto thank you for replying, I understood it completely wrongly previously so I was very confused. But now I completely understand the solution.. :D This is very helpful btw!
Can someone explain the const string& trick to me again? Isn't the reverse() still O(N)?
you are a fucking legend
Thank you for the explanation..... Hoping you will make more tutorials for beginner's like me...
So, something at this level or easier?
@@Errichto same level, also tips on data structures/algo if possible. You know like how to approach the problems with specific ds. Thanks for the reply.
For me, something at this level is great! But easier things would be awesome too
Came here for Manacher's but learnt a lot of new things 🙂.Beauty😎
Great explanation Errichto! Loved it! ❤
"longest palindromic substring is a quite easy problem..." bruh wut
lol bro....
Lol no way I'd figure this out in a technical interview if I didn't study it.
Loved it, good job. One small observation, the string "aaaaaa....aaaaa" is a degenerate case for time in your algorithm. Instead of iterating mid in 0, 1, 2, 3, 4, 5..... you could iterate mid in n/2, n/2 + 1, n/2 - 1, n/2 + 2, n/2 - 2, ....
Then just check if mid is far enough away from the edges to make a possible new best. That puts you really close to O(n) .
Sure, but then there can for sure be something similar to aaa...aa that will still be slower. It just shows that a problem author has a hard job of creating good tests :D
I don't get why binary search works. Data is not sorted. Wtf
Wow, your tutorial is so cool, it gives me a more general solution for optimization which could be applied to other Leetcode problems.
Can you make a video on how to get started in programming and also competitive programming, from zero to hero, how to reach at your level???
Goto any coding platform I prefer leetcode, select the difficulty to easy initially.
First and foremost, make a habit of solving problem by thinking out loud, marker and board or pen and paper, DO use it, I repeat, USE MARKER AND BOARD OR PAPER AND PEN BEFORE EVEN LAYING YOUR HANDS ON THE KEYBOARD.
Work our the problem slowly.
This is the key. I used to jump straight to keyboard when I started doing competitive coding.
Using the pen and paper beforehand to workout the problems (the process) builds problem solving networks in your head.
Good luck!
Don't give up!!
@@vivekchoudhary8745 thanks for the big reply, I will try to make a habit of pen n paper and practice.
@@mahesh4274 I'd be super glad if I could help others, also, as you progress further you will realize that there are different domains of problems, like graph problems, string related problems, array, tree or hash etc. try to find the out which part is your weakest work on it.
fight onn!!
Look at the Getting Started section in his github repo.
If you want a good book download competitive programmer's handbook and practise codeforces, USACO, ACM problems, if youre prepping for olympiads, if for an interview, do some leetcode too.
@@vivekchoudhary8745 I just started programming, but I will try to help if I can, I will try to create a blog or youtube channel to share knowledge..
My first thought was hashing.
It's possible to hash the string and hash the reversed string.
Then to find the longest palindrome, we can for every mid point (or double mid points for even length palindromes) iterate over it's prefixes and suffixes and compare them using hashes.
Now add binary search and we don't have to do that for every pref/suf length and just for O(logn) of them.
If I am not mistaken the total complexity would be O(n*logn)
On the other hand hashes can collide so it's kinda randomised.
But still, risk is pretty low and can be further lowed by using pairs of hashes.
You are completely right, and we can even get O(N) with hashes if we increment the answer by 1 instead of binary searching :)
I just didn't want to talk about hashes in this video, too many things for a beginner's problem.
"we can for every mid point (or double mid points for even length palindromes) iterate over it's prefixes and suffixes and compare them using hashes."
I don't understand this sentence. What do you mean by "it's prefixes"? By "it" do you mean "mid point"? If so, then what do you mean by a "prefix/suffix of a mid point"?
@@Errichto Can you please explain O(N) approach using hashes or can you give some reference to any blog or article where it is discussed ? I can only figure out O(NLogN) approach using hashes :(
@@praveenojha33 O(n) approach is Manacher's algorithm
Sir,it was really good.
Never thought of binary search 🥺
Can anyone explain to me the parity concept here?
not a quite easy problem though
Please explain O(N) solution
@8:20 Binary search explanation
Funny thing: if you implement this solution in Swift language, it won't be accepted due to exceeded time. Test case has 1000 "a" chars string. I guess the only option is to go with a suffix tree then.
Thanks this is faster than normal dp
Sir thanku so much for your videos ,sir I have completed the basics and now when I try to solve medium level question at codechef I get stuck maximum times only 1-2 questions per day can be solved.. This is my hackerank profile : www.hackerrank.com/profile/samarLove
could you please tell me what I should I do next .
I am not progressing now as fast I should be...
I got the first for-loop...it takes every element and expands towards the right and left side to get the largest palindrome...but can anyone explain the purpose of the second for loop?.
I'm doing this problem for the last 20 mins, and it seems that the test case no 26('abb') is giving me the wrong result. When I checked it by inputting the input in the test case, it's giving me the correct answer. Anyone can explain to me why is it happening?
guys , what does this mean i'm seeing this for the first time
for(int parity: {0,1} )
{
}
is this a cpp thing?
This should be a paid content
string substr allocates a new string. string_view, span or plain pairs of pointers should be used in examples like this, for constant time.
thank you for the lovely 25 minute explanation even though i know you can do this in 25 seconds. you are truly a gift to us all who enjoy competitive programming.
p.s. i finally solved my first problem solved in under 5 minutes during a 3-problem online assessment, and boy did it feel amazing! Too bad the other two took about an hour each because i got ahead of myself after the first solution :P
The high is amazing when you solve a (relative difficult ) problem. The low is terrible when you trying to understand a solution or freeze in interview.
quite easy.......unintentional flex
You are awesooome, thank you. I love that you first write the naive solution and then explain and improve the code bit by bit :3
Can anyone tell in the binary search method why we change the low and high value if it is not match with parity and we also increase the mid value if it is not match with parity instead of that can we only modify the mid value if it is not match with the parity..
Please correct me if i am wrong.
Hi @Errichto, I'm wondering how making change to parameter type: (string s) -> (const string& s) would let a for loop exit with early condition hence faster-than-linear runtime. @5:58. Do you mean such change is coming from the algorithmic change and changing the paramter type would only save CPU from using extra memory to take in s? or is there something special about how for loop treats a reference ? Thanks for your time in advance
Hey can u suggest a book for solving problems using methods like the monarch think u talked abt
can someone explain the n2logn solution in detail. How is Binary search used here?
damn amazing i just did this question today but your dynamic programming solution is faster than mine, amazing
love ur videos bro, didnt quite understand in binary search part tho, maybe with a little bit more replay i can understand it, thank you for the video!
Hello Errichto...Kindly upload videos on greedy strategy...I have solved more than 100 Div2C problems...yet whenever a greedy comes even in B ,I cant figure out whether greedy will work or not...or to which variable I should do greedy on.
It's 02:33 AM and holy Jesus why tf I couldn't get past the first approach. ^_^
Can anyone please explain why we add 1 in the mid-x+1? I am not able to figure it out.
could u please once more explain that parity thing ..please!!!!!!!!!
Can u do The Skyline Problem it may be easy for you because you are the Godfather of Computational Geometry but it freaks me out xd
One Errichto video teach you a lot of extra things along with the actual solution.
The C++ optimization's rly helpful
Just realised how much cpp is faster then python :O
plz make a video on greedy problems, i just don't know how to go about it.. always loved ur channel , thanks in advance
"binary search over the answer is the common technique,"
This is the best explaination i have heard so far...plzzz me lots of videos it will be helpful for my upcoming interviews.
Sir I Would request you to post a solution for CodeForces Contest 615 Div.2 Problem 1
I really loved the video
Can anyone explain in details about the parity logic?
How to solve this problem using suffix array?
I am currently through to the national finals of the informatics olympiad, but I'm not sure how to practice for it. Any tips or ideas?
We love youuuuu
the appropriate playpack speed is advised to be 0.5
Please use the word "lemma" in your next video. It is a really funny sounding word.
Hi Errichto
good explation
It's like watching sachin tendulkar doing batting or roger federrer playing tennis.Pure legend
nice explanation
It is the best video I've ever seen for this problem. Your approach is awesome dude.
Helpful information thankyou
Thanks for the explanation. I came to watch your video after I solved the problem myself. I was not disappointed because you explored many options. For N^2 time complexity what I did was reversed the original string and used longest common substring between the original string and the reversed string. I got an edge case where it was finding strings of length 2 to be palindrome even if they were not.
You are very smart. Great explanation
What software do you use to record yourself and screen on Ubuntu? Well done by the way.
Thanks :)
I thought you will solve by manacher's algorithm
I like u
Excellent video !! need to bring back the second errichto
God.
Hoped u would have covered manarch's algorithm as well!!!!