Leetcode problem Longest Palindromic Substring (two solutions)
Вставка
- Опубліковано 5 жов 2024
- Solving a medium coding interview question from Leetcode leetcode.com/p...
Final code: github.com/Err...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
Github repository: github.com/Err...
Second YT channel for streams: / errichto2
FB and Twitter: / errichto & / errichto
Frequently Asked Questions: github.com/Err...
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.
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.
Wow, no ads in any video.... This man is a legend
Thank you brother from another mother, everyone on UA-cam showing the code of optimised approach,
Only you showed the brute force
I wish you covered the Manacher's algorithm as well.
yes!
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!
Great stuff, Errichto! There are far more successful UA-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'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.
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.
Your explanations of problems are awesome going from bruteforce approach to optimisation......
Thank you so much for these Leetcode tutorials. Absoultely love them !
Mindblowing sir .
Thankyou very much .
Your way of explaination is unique.
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.
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
One Errichto video teach you a lot of extra things along with the actual solution.
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.
errichto makes me wanna leave programming and love programming at a same time..
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.
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.
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.
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
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
This is so informative and awesome!
Thank you :)
Wow, your tutorial is so cool, it gives me a more general solution for optimization which could be applied to other Leetcode problems.
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
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!!
Great explanation Errichto! Loved it! ❤
Came here for Manacher's but learnt a lot of new things 🙂.Beauty😎
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
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
damn amazing i just did this question today but your dynamic programming solution is faster than mine, amazing
It is the best video I've ever seen for this problem. Your approach is awesome dude.
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.
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.
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?
Thx for the tutorial. I would appreciate it if you continue to share well known topics.
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
The C++ optimization's rly helpful
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..
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)
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!
string substr allocates a new string. string_view, span or plain pairs of pointers should be used in examples like this, for constant time.
helpful details, that was amazing
plz make a video on greedy problems, i just don't know how to go about it.. always loved ur channel , thanks in advance
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
U r such a good teacher bro
Can you please make a video on Manacher's Algorithm Errichto?
watching you makes me think of quitting my job
Sir,it was really good.
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!
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.
Need More Videos Like this
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.
You are very smart. Great explanation
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!
What software do you use to record yourself and screen on Ubuntu? Well done by the way.
Please explain O(N) solution
It's like watching sachin tendulkar doing batting or roger federrer playing tennis.Pure legend
Sir I Would request you to post a solution for CodeForces Contest 615 Div.2 Problem 1
I really loved the video
Thanks this is faster than normal dp
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
06:08 why does comparing by reference is faster than comparing two string variables?
could u please once more explain that parity thing ..please!!!!!!!!!
you are a hero!
I still didn't understand parity and binary search based solution to this problem. Any good materials for this to read & analyse?
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?.
Never thought of binary search 🥺
Helpful information thankyou
thanks a lot your great work!
No need to write O(n2) code twice :
Approach:
Consider every index as a center/mid,expand around the center to find the pallindrome.Mark the empty spaces as '# or any special character.Basically it has done for the even length string.
string longestPalindrome(string s) {
int n=s.size();
string res;
res+='#';
for(int i=0;i
really good explaination
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.
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?
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?
Hey can u suggest a book for solving problems using methods like the monarch think u talked abt
Great tutorial
I thought you will solve by manacher's algorithm
nice explanation!
Can anyone explain in details about the parity logic?
How to solve this problem using suffix array?
Can anyone please explain why we add 1 in the mid-x+1? I am not able to figure it out.
We love youuuuu
@8:20 Binary search explanation
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.
It's 02:33 AM and holy Jesus why tf I couldn't get past the first approach. ^_^
Can someone explain the const string& trick to me again? Isn't the reverse() still O(N)?
What does the parity means in this video?
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
nice explanation
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.
can someone explain the n2logn solution in detail. How is Binary search used here?
the appropriate playpack speed is advised to be 0.5
guys , what does this mean i'm seeing this for the first time
for(int parity: {0,1} )
{
}
is this a cpp thing?
I don't get why binary search works. Data is not sorted. Wtf
Is there any algorithm, that could be a efficient replacement for Longest Common Substring with k-mismatches
yes
@@chienglsictfried1858 and that will be???