Leetcode problem Longest Palindromic Substring (two solutions)
Vložit
- čas přidán 10. 01. 2020
- Solving a medium coding interview question from Leetcode leetcode.com/problems/longest...
Final code: github.com/Errichto/youtube/b...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Second YT channel for streams: / errichto2
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
![Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]](http://i.ytimg.com/vi/DK5OKKbF6GI/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 :)
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.
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!
I really appreciate your videos. I think the intuition behind how you derive the solution is outstanding. Helps a lot to understand how you came develop an approach.
Thank you brother from another mother, everyone on CZcams showing the code of optimised approach,
Only you showed the brute force
Great stuff, Errichto! There are far more successful CZcamsrs 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! 😀
Thank you so much for these Leetcode tutorials. Absoultely love them !
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.
Wow, no ads in any video.... This man is a legend
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.
I loved your way of breaking down the problem and gradually moving towards more optimized version. Would love your input on codechef problems from long challenge, cook off, lunchtime and various other categories of problem.
Wow, your tutorial is so cool, it gives me a more general solution for optimization which could be applied to other Leetcode problems.
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
Thx for the tutorial. I would appreciate it if you continue to share well known topics.
It is the best video I've ever seen for this problem. Your approach is awesome dude.
Your explanations of problems are awesome going from bruteforce approach to optimisation......
Mindblowing sir .
Thankyou very much .
Your way of explaination is unique.
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.
Excellent video !! need to bring back the second errichto
This is the best explaination i have heard so far...plzzz me lots of videos it will be helpful for my upcoming interviews.
I wish you covered the Manacher's algorithm as well.
yes!
damn amazing i just did this question today but your dynamic programming solution is faster than mine, amazing
One Errichto video teach you a lot of extra things along with the actual solution.
This is so informative and awesome!
Thank you :)
helpful details, that was amazing
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
Some cool modern C++ tricks: is_palindrome could be written w/ std::equal() and rbegin(),rend(). string_view could be used to get "substrings" in constant time. I think std::binary_search() could also be applied w/ the is_palindrome predicate.
Came here for Manacher's but learnt a lot of new things 🙂.Beauty😎
U r such a good teacher bro
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.
You are very smart. Great explanation
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!
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
The C++ optimization's rly helpful
Sir,it was really good.
plz make a video on greedy problems, i just don't know how to go about it.. always loved ur channel , thanks in advance
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!!
thanks a lot your great work!
What software do you use to record yourself and screen on Ubuntu? Well done by the way.
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?
Hey can u suggest a book for solving problems using methods like the monarch think u talked abt
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.
Need More Videos Like this
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
can someone explain the n2logn solution in detail. How is Binary search used here?
Hoped u would have covered manarch's algorithm as well!!!!
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.
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.
Can anyone please explain why we add 1 in the mid-x+1? I am not able to figure it out.
really good explaination
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.
@@JV-fm5ul but why he did even odd thing
you are a hero!
errichto makes me wanna leave programming and love programming at a same time..
I still didn't understand parity and binary search based solution to this problem. Any good materials for this to read & analyse?
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
In contests like codejam and kickstart how often we need to check our program by writing brute force solution and finding cases where our optimal solution is giving WA...
Have you used this method of checking programs in short contests also..
Codejam and Kickstart have feedback for small constraints so it isn't that important. Maybe useful if you want to find that countertest.
nice explanation!
Helpful information thankyou
How to solve this problem using suffix array?
Thanks this is faster than normal dp
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?.
Great tutorial
What does the parity means in this video?
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.
nice explanation
Can someone explain the const string& trick to me again? Isn't the reverse() still O(N)?
06:08 why does comparing by reference is faster than comparing two string variables?
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.
good content, you rock
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
We love youuuuu
Can you please make a video on Manacher's Algorithm Errichto?
Please explain O(N) solution
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
Can anyone explain in details about the parity logic?
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?
watching you makes me think of quitting my job
Is there any algorithm, that could be a efficient replacement for Longest Common Substring with k-mismatches
yes
@@chienglsictfried1858 and that will be???
good explation
guys , what does this mean i'm seeing this for the first time
for(int parity: {0,1} )
{
}
is this a cpp thing?
Sir I Would request you to post a solution for CodeForces Contest 615 Div.2 Problem 1
I really loved the video
Thanks :)
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 anyone explain to me the parity concept here?
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
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?
Thanks for your explanation! A quick note: @19:04, I don't think it's N positions, but rather 2N-1 positions (because middles can be spaces between characters)
string substr allocates a new string. string_view, span or plain pairs of pointers should be used in examples like this, for constant time.
I thought of a content suggestion, some of the "hacking" rules sound fun. It might be cool to make a video where you go through some of the winner's submissions and try to find counter examples for them. I think it wouldn't be rude if you only went after the winners, or maybe if you are friends with any of them ask them if they mind.
They don't often submit incorrect ideas ;p strong participants have good intuition and they can prove their solution. It would be much easier to look through their wrong submissions though, but maybe I will just discuss my own mistakes?
@@Errichto We don't make mistakes, we just have happy accidents!
Hi Errichto
So cool
Legend
you are a fucking legend
thansk
It's 02:33 AM and holy Jesus why tf I couldn't get past the first approach. ^_^
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
Never thought of binary search 🥺
could u please once more explain that parity thing ..please!!!!!!!!!