Wouldn't this solution be O(n^3) because s[l:r+1] could make a copy of s for each iteration? An improvement would be to store the indices in variables like res_l and res_r when there is a larger palindrome instead of storing the string itself in res. Then, outside of the loops, return s[res_l:res_r].
Good catch! you're exactly correct, and your proposed solution would be O(n^2). I hope the video still explains the main idea, but thank you for pointing this out. I will try to catch mistakes like this in the future.
Hey Devon Fulcher, Hii, if you don't mind can you please share your code, it would increase my knowledge in approaching these huge time complexity questions
@@shivakumart7269 Here you go leetcode.com/problems/longest-palindromic-substring/discuss/1187935/Storing-string-indices-vs.-using-substring! My small fix doesn't seem to make the runtime much faster in terms of ms but it is more correct in terms of algorithmic complexity.
Hi Devon, do you mind explaining why s[l:r + 1] would result in a O(N^3)? How does making a copy of s for each iteration make the solution worse? Thank you.
On the Neetcode Practice page, this problem is listed as 1-D Dynamic Programming. But this video doesn't use DP at all. Also, 1-D DP yields an O(n) solution, if we can calculate each table entry in constant time. But the solution in this video is O(n^2).
Hi everybody I want to share the answer to this problem using dp, the code is well commented (I hope), also congrats @NeetCode for his excellent explanations def longest_palindromic_substring(s): n = len(s) if n == 1: return s dp = [[False] * n for _ in range(n)]# 2D array of n x n with all values set to False longest_palindrome = ""
# single characters are palindromes for i in range(n): dp[i][i] = True longest_palindrome = s[i]
# check substrings of length 2 and greater for length in range(2, n+1): # size of the window to check for i in range(n - length + 1): # iteration limit for the window j = i + length - 1 # end of the window if s[i] == s[j] and (length == 2 or dp[i+1][j-1]): # dp[i+1][j-1] this evaluates to True if the substring between i and j is a palindrome dp[i][j] = True # set the end points of the window to True if length > len(longest_palindrome): longest_palindrome = s[i:j+1] # update the longest palindrome
return longest_palindrome print(longest_palindromic_substring("bananas")) # Output: 'anana' # The time complexity of this solution is O(n^2) and the space complexity is O(n^2).
Thanks for the amazing explanation. I also have a quick comment. In the while loop, we can add a condition to exit the loop once the resLen variable reaches the maximum Length(len(s)). By doing this, we can stop the iteration once the given entire string is a palindrome and skip iterating through the right indices as the middle element. [while l>=0 and r< len(s) and s[l] == s[r] and resLen!=len(s)]:
time complexity = O(|s|^2) spcae complexity = O(1) class Solution { private: string expandAroundCenter(string s, int left, int right) { int n = s.length(); while (left >= 0 && right < n && s[left] == s[right]) { left--; right++; } return s.substr(left + 1, right - left - 1); } public: string longestPalin (string S) { int n = S.length(); if (n < 2) { return S; } string longestPalindrome = S.substr(0, 1); // default to the first character for (int i = 0; i < n - 1; i++) { string palindromeOdd = expandAroundCenter(S, i, i); if (palindromeOdd.length() > longestPalindrome.length()) { longestPalindrome = palindromeOdd; } string palindromeEven = expandAroundCenter(S, i, i + 1); if (palindromeEven.length() > longestPalindrome.length()) { longestPalindrome = palindromeEven; } } return longestPalindrome; } };
Thanks (this isn’t a dynamic programming problem but it’s marked as dynamic programming on neetcode website) TODO:- take notes in onenote and implement Trick is to expand outward at each character (expanding to the left and right) to check for palindrome. BAB if you expand outward from A you will check that left and right pointers are equal, while they’re equal keep expanding. WE DO THIS FOR EVERY SINGLE INDEX i in the string. BUT this checks for odd length palindromes, we want to also check for even length so we set the left pointer to i and the right pointer to i+1 and continue expanding normally. For index i set L,R pointers to i then expand outwards, and to check for even palindrome substrings set L=i, R=i+1
@@satyamkumarjha8152 DP is o(n^2) time and space, the most optimal solution is the algorithm in this video except saving L, R indices of res instead of the whole string, which is o(n^2) time and o(1) space
I was using while left in range(len(s)) and it definitely make my solution hit the time limit. Able to pass the test cases after change it to left > 0. Thanks Neet!
Thanks this is definitely a different kind of solution, especially for a dynamic programming type problem but you explained it and made it look easier than the other solutions I've seen. Also for people wondering, the reason why he did if (r - l + 1), think about sliding window, (windowEnd - windowStart + 1), this is the same concept, he is getting the window size aka the size of the palindrome and checking if its bigger than the current largest palindrome.
For me it was the separating out of even versus odd checking. I was moving my pointers all at once, thus missing the edge case where longest length == 2 (e.g. 'abcxxabc'). While separating out duplicates code, it does do the trick.
I had the same question. The reason it can be considered DP is because when we expand outwards by one character, the check for whether it's a palindrome is O(1) because we rely on the previous calculation of the inner string of characters. Relying on a previous calculation like that is the basis of dynamic programming. This optimization is critical as it brings the solution down from O(n^3) to O(n^2).
I like when you post that it took time to you also to solve it, many people, including me, we get scaried if we do not solve it fast as "everybody does"!! Thanks again.
This is two pointer problem instead of DP problem no? It doesn't really solve subproblem and does not have recurrence relationship. The category in the Neetcode Roadmap got me. I spent quite a while trying to come up with the recurrence function but no avail :D
The way I solved it to create a dp table. The function is dp[i,j] = true if i == j Else true if s[i] == s[j] and inner substring is a plaindrome too (i e dp[i+1][j-1]
what i did was expand the center first( find the cluster of the center character - "abbba", in the given example find the index of the last b), then expand the edges, that way its irrelevant if its even or odd, each iteration will start from the next different character.
But unfortunately string slice operation would also cost linear time as well so u can store the range index instead of updating the res with string everytime
Thanks for the amazing explanation! I managed to double the performance by doing this: While iterating s, you can also check if s itself is a palindrome, and if so, you don't need to iterate the other half of it (since s will be the largest palindrome, and therefore be the answer).
Hello neetcode, thanks for all the AMAZING work you do here. I've been trying to come up with a solution of my own for this question and it's been sad to say the least. I tried coming up with a solution of my own because even if your solutions (especially the brute for solution) makes sense, the time complexity O(n^3) is scary. In short, it's the firs time I've ever seen a problem that could ever have such time complexities. I actually saw this problem on leetcode before even knowing you had solved it before. So I would like to ask, do you think it's fine "learning" the brute force approach and trying the brute force approach first for all problems? Or do you just start with an optimised solution? I'm asking because it's tempting to try out a more efficient approach or a better data structure than when you try to do so with brute force. I also find myself having tunnel vision at times when I am trying the brute force approach. Thank you so much for everything you do here again and I really hope you could ever respond to this :)
If the input is "ac", the answer will go wrong due to the result should be "a" or "c". This question should point out whether a single letter can be a palindrome.
The solution is crystal clear and very easy to understand, although I'm still confused why is this problem placed under Dynamic Programming category? Can anyone explain?
This one doesn't seem to be related much to the dynamic programming stuff.. the most intuitive way to me is the same, expanding from the centre part. Thanks for your video man, it is the clearest implementation I have ever met. I implemented with the same idea, but stumble a lot and ended up with a long code(maybe because I was using pure C.. xD)
Really cool video, thanks for walking through it. Question: Is there a reason to track resLen or would it be just as efficient to use len(res) instead?
Got this question in Leetcode's mock online assessment and had no idea that it was a medium. I didn't even know where to begin. I guess I still need to keep doing easy before I move on to the mediums.
how would it get whether the string will go in first while loop or second while loop as no condition is mentioned for checking even or odd length . I am not able to get it
This is an awesome explanation, thank you so much for doing it. I couldn't figure out the edge cases, I initially did it using recursion and memo. By the way, quick question shouldn't the for loop be for i in range(len(s)-1) in order to prevent out-of-index error on the string since r is being incremented? Thank you.
@@NotAmour thank you for responding, after reviewing my comment I realized where I went wrong. Again thank you so much for these videos they’re beyond helpful. :)
For neetcode solution, I think we could set an expanded step to cache the longest palindrome we have found for improving. Cause if we have found a 3 length palindrome already, then we do not have to do it again. I believe that gonna save a lot of time.
hey neet code for the even string "adam" "ada" forms a palliamdrom; I could not get the code the work with this logic for even length string with substrings having palliandrome. Also how is l,r set to the middle when you are setting the index to start at 0?
I am pretty sure my duct tape solution is O(N^3) but it still barely made the Time limit so I am here checking how one could solve it better. Making a center pivot and growing outwards is a very elegant solution indeed
I'm new to leetcode but this was in your dynamic programming playlist, is this solution involving DP? great explanation btw this is the only video regarding this problem i could understand
the solution isn't dp but you can solve it with dp approach. But, I don't think you can pass all the test with dp because of Exceed Time Limited, my dp approach only passed 147 / 180
I tried so hard with recursive calls and cache, thank you for the explanation! I wonder why I never come up with that clever idea though. I thought about expanding out from the center, but I was trying to find "the center (of answer)" and expand out only once.
Very good solution. If you add at the beginning of for loop the line "if resLen > 0 and len(s) - i - 1 < resLen // 2 : break" you will speed up the algorithm faster than 90 % submissions and get a runtime of about 730 ms. The idea is if you already have the palindrome you don't have to loop till the end of "s". You can break the loop after the distance till the end of "s" is less than resLen / 2.
I didn't get the part where you say that you would be starting from the mid position and will travel both sides i.e left and right but you also start your pointers from the starting point i.e 0. Could you please explain how exactly this works? I have watched your video thrice but cannot understand how exactly it is working. I want to understand where is the mid point because since l pointer is already 0 it would keep decrementing i.e -1. That is what I am able to understand.
# 5. Longest Palindromic Substring def longestPalindrome(self, s: str) -> str: res = "" resLen = 0 start, end = 0, 0 # algo - O(n^2) - starting from the at the chara and expanding outwards # 2 cases - even and odd len palindrome for i in range(len(s)): # odd len l, r = i, i # while pointer is still in bound and is a palindrome while l >=0 and r resLen): start = l end = r+1 resLen = r-l+1 l-=1 r+=1 # even len l, r = i, i+1 while l>=0 and r resLen): start = l end = r+1 resLen = r-l+1 l-=1 r+=1
Bro i have a doubt l,r= i,i And after some line of code we write l,r=i,i+1 So didn't the second l,r will overwrite the first l,r Since python runs the code line by line so why not this will happen ?
Can someone walk through what the condition if(r-l + 1) is yielding, because when I dryrun it it seems to give 1 for each iteration which would not be greater than resLength. Feeling a little confused as to how this line of code plays out in real time
NC is checking the case where the palindromic substring is of even number in character length. In order to check that, you need to have p1 pointing to i and p2 pointing to i + 1. p2 can be i -1. It depends how you want to solve the problem. For example, say we have abba. In order to spot, "abba", you need p1 = 1 and p2 = 1 + 1 = 2. You can't get abba, if both of your pointers, p1 and p2 are 1.
anyone can help explain why the solution were able to tell if s is even number or odd number length? i was thinking we needed to check that with modulus. thanks
it's quite simple it you draw a square matrix of cases where rows and cols are each character of string. for the first case where your final answer is a palidrome with odd length, you alway start from the diagonal line of the matrix and expand around the center in the same speed. that's why l and r are set to the same index for the second case where your palindrome is even length, you would start from two points along the diagonal but now two parallel lines then start expand the same
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
@NeetCode make a video on Manachar's algo. I couldn't wrap my head around it
Wouldn't this solution be O(n^3) because s[l:r+1] could make a copy of s for each iteration? An improvement would be to store the indices in variables like res_l and res_r when there is a larger palindrome instead of storing the string itself in res. Then, outside of the loops, return s[res_l:res_r].
Good catch! you're exactly correct, and your proposed solution would be O(n^2). I hope the video still explains the main idea, but thank you for pointing this out. I will try to catch mistakes like this in the future.
Hey Devon Fulcher, Hii, if you don't mind can you please share your code, it would increase my knowledge in approaching these huge time complexity questions
@@shivakumart7269 Here you go leetcode.com/problems/longest-palindromic-substring/discuss/1187935/Storing-string-indices-vs.-using-substring! My small fix doesn't seem to make the runtime much faster in terms of ms but it is more correct in terms of algorithmic complexity.
@@devonfulcher It says, topic does not exist
Hi Devon, do you mind explaining why s[l:r + 1] would result in a O(N^3)? How does making a copy of s for each iteration make the solution worse? Thank you.
I looked at solutions from other people, but your explanation was the. best. In 8 mins, you explained a 30 min solution.
On the Neetcode Practice page, this problem is listed as 1-D Dynamic Programming. But this video doesn't use DP at all. Also, 1-D DP yields an O(n) solution, if we can calculate each table entry in constant time. But the solution in this video is O(n^2).
I'm glad to see that I'm not the only one confused here.
Hi everybody I want to share the answer to this problem using dp, the code is well commented (I hope), also congrats @NeetCode for his excellent explanations
def longest_palindromic_substring(s):
n = len(s)
if n == 1:
return s
dp = [[False] * n for _ in range(n)]# 2D array of n x n with all values set to False
longest_palindrome = ""
# single characters are palindromes
for i in range(n):
dp[i][i] = True
longest_palindrome = s[i]
# check substrings of length 2 and greater
for length in range(2, n+1): # size of the window to check
for i in range(n - length + 1): # iteration limit for the window
j = i + length - 1 # end of the window
if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
# dp[i+1][j-1] this evaluates to True if the substring between i and j is a palindrome
dp[i][j] = True # set the end points of the window to True
if length > len(longest_palindrome):
longest_palindrome = s[i:j+1] # update the longest palindrome
return longest_palindrome
print(longest_palindromic_substring("bananas"))
# Output: 'anana'
# The time complexity of this solution is O(n^2) and the space complexity is O(n^2).
Thanks, this is what i came for.
Thanks for the amazing explanation. I also have a quick comment. In the while loop, we can add a condition to exit the loop once the resLen variable reaches the maximum Length(len(s)). By doing this, we can stop the iteration once the given entire string is a palindrome and skip iterating through the right indices as the middle element. [while l>=0 and r< len(s) and s[l] == s[r] and resLen!=len(s)]:
I've been scratching my head on this problem for a few days thank you for your clean explanation and video!
Love your vids. I swear you're the best leetcode tutorial out there. You get to the point and are easy to understand.
It's also super useful that he explains the time complexity of the solutions.
man I have the exact feeling!!!
I only check this one channel for all questions
time complexity = O(|s|^2)
spcae complexity = O(1)
class Solution {
private:
string expandAroundCenter(string s, int left, int right) {
int n = s.length();
while (left >= 0 && right < n && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left + 1, right - left - 1);
}
public:
string longestPalin (string S) {
int n = S.length();
if (n < 2) {
return S;
}
string longestPalindrome = S.substr(0, 1); // default to the first character
for (int i = 0; i < n - 1; i++) {
string palindromeOdd = expandAroundCenter(S, i, i);
if (palindromeOdd.length() > longestPalindrome.length()) {
longestPalindrome = palindromeOdd;
}
string palindromeEven = expandAroundCenter(S, i, i + 1);
if (palindromeEven.length() > longestPalindrome.length()) {
longestPalindrome = palindromeEven;
}
}
return longestPalindrome;
}
};
Thanks (this isn’t a dynamic programming problem but it’s marked as dynamic programming on neetcode website)
TODO:- take notes in onenote and implement
Trick is to expand outward at each character (expanding to the left and right) to check for palindrome. BAB if you expand outward from A you will check that left and right pointers are equal, while they’re equal keep expanding. WE DO THIS FOR EVERY SINGLE INDEX i in the string.
BUT this checks for odd length palindromes, we want to also check for even length so we set the left pointer to i and the right pointer to i+1 and continue expanding normally.
For index i set L,R pointers to i then expand outwards, and to check for even palindrome substrings set L=i, R=i+1
This can be solved with dp though
@@felixtheaeven faster?
@@samuraijosh1595 yes,the solution proposed in this video takes n^3 time complexity whereas the solution using dp takes only n^2
@@satyamkumarjha8152 DP is o(n^2) time and space, the most optimal solution is the algorithm in this video except saving L, R indices of res instead of the whole string, which is o(n^2) time and o(1) space
I was using while left in range(len(s)) and it definitely make my solution hit the time limit. Able to pass the test cases after change it to left > 0. Thanks Neet!
Thanks this is definitely a different kind of solution, especially for a dynamic programming type problem but you explained it and made it look easier than the other solutions I've seen.
Also for people wondering, the reason why he did if (r - l + 1), think about sliding window, (windowEnd - windowStart + 1), this is the same concept, he is getting the window size aka the size of the palindrome and checking if its bigger than the current largest palindrome.
Good explanation! I thought the palindrome for the even case would be a lot more complicated but you had a pretty simple solution to it great vid!
For me it was the separating out of even versus odd checking. I was moving my pointers all at once, thus missing the edge case where longest length == 2 (e.g. 'abcxxabc'). While separating out duplicates code, it does do the trick.
Why is this considered to be a dynamic programming example?
It is
Great question, I’m wondering the same
There is a DP way to do it you can put all the substrings in a dp table and check for if it’s palindrome
This solution is without dp, it can be solved with dp too but this isn’t it
I had the same question. The reason it can be considered DP is because when we expand outwards by one character, the check for whether it's a palindrome is O(1) because we rely on the previous calculation of the inner string of characters. Relying on a previous calculation like that is the basis of dynamic programming. This optimization is critical as it brings the solution down from O(n^3) to O(n^2).
This was definitely the best way to finish my day, with an AWESOME explanation
You are the GOAT. Any leetcode problem I come here and 95% of time understand it
I've watched several video solution on this problem and yours is the easiest to understand. Thanks a lot!
I like when you post that it took time to you also to solve it, many people, including me, we get scaried if we do not solve it fast as "everybody does"!! Thanks again.
you're my leetcode savior!
Haha I appreciate it 😊
This is two pointer problem instead of DP problem no?
It doesn't really solve subproblem and does not have recurrence relationship. The category in the Neetcode Roadmap got me. I spent quite a while trying to come up with the recurrence function but no avail :D
The way I solved it to create a dp table. The function is
dp[i,j] = true if i == j
Else true if s[i] == s[j] and inner substring is a plaindrome too (i e dp[i+1][j-1]
Great explanation. I was struggling with this one even after looking at answers.
Just like another guy said, his explanation is well packed, straight to the point. Please keep up the good work. 🔥🔥🔥
Thank you! Great work and very clear explanation.
Your explanation saved my life!!! Thank youuuu! I like how you explain you look at this question.
Tons of thanks for making these videos. This is really very helpful and video explanation is very nice . optimize and concise
really enjoy your content, super informative! keep them coming
an actual beast. i had to look up the list slicing because i thought the [:stop:] value was inclusive. thanks for the great content
Amazingly neat solution and enlightening explanation as always!
what i did was expand the center first( find the cluster of the center character - "abbba", in the given example find the index of the last b), then expand the edges, that way its irrelevant if its even or odd, each iteration will start from the next different character.
you set the l,r = i,i how is it middle
thanks neetcode you're out here doing holy work
Thank you for this! Great concise explanations. Subscribed!
But unfortunately string slice operation would also cost linear time as well so u can store the range index instead of updating the res with string everytime
Thank you very much for your videos mate. Just wondering what software you are using to draw on? it looks very nice.
thanks for being honest and telling us that it took you a while to figure this out. It is empowering ngl
Thank you for sharing a good idea. I am so enjoying to learn.
Wait, why is this classified as a DP problem? Your solution was my first thought -- and what I ended up implementing, thinking it was incorrect.
Such amazing code. I have same idea as yours but unable to write such a concise code. AWESOME
Thanks for the amazing explanation!
I managed to double the performance by doing this: While iterating s, you can also check if s itself is a palindrome, and if so, you don't need to iterate the other half of it (since s will be the largest palindrome, and therefore be the answer).
Great explanation and easy to understand. Thanks for the video
Hello neetcode, thanks for all the AMAZING work you do here. I've been trying to come up with a solution of my own for this question and it's been sad to say the least. I tried coming up with a solution of my own because even if your solutions (especially the brute for solution) makes sense, the time complexity O(n^3) is scary. In short, it's the firs time I've ever seen a problem that could ever have such time complexities.
I actually saw this problem on leetcode before even knowing you had solved it before. So I would like to ask, do you think it's fine "learning" the brute force approach and trying the brute force approach first for all problems? Or do you just start with an optimised solution? I'm asking because it's tempting to try out a more efficient approach or a better data structure than when you try to do so with brute force. I also find myself having tunnel vision at times when I am trying the brute force approach.
Thank you so much for everything you do here again and I really hope you could ever respond to this :)
Wow! Just love the way you explain.
Thanks, that was a super easy explanation!💖
how does it know it begins at middle?
I see acceptance rate of this question making me nervous, but see your explanation make me feel relieved :)
hey buddy u earned my subs!! your explanation is very awesome keep going love your content😘
If the input is "ac", the answer will go wrong due to the result should be "a" or "c". This question should point out whether a single letter can be a palindrome.
Great explanation! By far the best solution.
i don't know ...how i will thanks to you for such wonderful videos !! appreciated
One of the best explaination so far
The solution is crystal clear and very easy to understand, although I'm still confused why is this problem placed under Dynamic Programming category? Can anyone explain?
This one doesn't seem to be related much to the dynamic programming stuff.. the most intuitive way to me is the same, expanding from the centre part. Thanks for your video man, it is the clearest implementation I have ever met. I implemented with the same idea, but stumble a lot and ended up with a long code(maybe because I was using pure C.. xD)
Really cool video, thanks for walking through it. Question: Is there a reason to track resLen or would it be just as efficient to use len(res) instead?
yes cuase this value is being updated everytime if there is a value that is bigger than what this var is already is havng uptill that point
Great explanation, as usual!
Amazing way to simmplify the problem
Brilliant Explanation bro. You got a new subscriber.Great job.
Thanks, glad it was helpful
thank you soo much , i was struggling for a long for this problem . peace finally .
Again thanks ❤
Wait a minute. I've been so conditioned to think O(n^2) is unacceptable that I didn't even consider that my first answer might be acceptable.
Thank you Neetcode for this video.
Got this question in Leetcode's mock online assessment and had no idea that it was a medium. I didn't even know where to begin. I guess I still need to keep doing easy before I move on to the mediums.
how would it get whether the string will go in first while loop or second while loop as no condition is mentioned for checking even or odd length . I am not able to get it
Very nice approach, thanks.
This is an awesome explanation, thank you so much for doing it. I couldn't figure out the edge cases, I initially did it using recursion and memo. By the way, quick question shouldn't the for loop be for i in range(len(s)-1) in order to prevent out-of-index error on the string since r is being incremented? Thank you.
Late response, but pythons range operator is inclusive on the left bound and exclusive on the right bound. Eg range(0, 2) -> [0, 1]
@@NotAmour thank you for responding, after reviewing my comment I realized where I went wrong. Again thank you so much for these videos they’re beyond helpful. :)
@@ryankawall3550 No worries, I'm glad you figured it out!
By the way I didn't make this video, haha
@@NotAmour haha oh man I thought the creator responded. Anyhow thanks a million for your response, much appreciated.
Amazing solution you have made.
For neetcode solution, I think we could set an expanded step to cache the longest palindrome we have found for improving. Cause if we have found a 3 length palindrome already, then we do not have to do it again. I believe that gonna save a lot of time.
hey neet code for the even string "adam" "ada" forms a palliamdrom; I could not get the code the work with this logic for even length string with substrings having palliandrome. Also how is l,r set to the middle when you are setting the index to start at 0?
best solution ever, thnx for making it looks easy
thanks for your explanation. my comment: instead of updating the resLen, you might just use len(res) to check for each if condition
I am pretty sure my duct tape solution is O(N^3) but it still barely made the Time limit so I am here checking how one could solve it better. Making a center pivot and growing outwards is a very elegant solution indeed
You are the best, thanks for this explanation, its very clear.
I think this solution is crazy - crazy awesome!
I'm new to leetcode but this was in your dynamic programming playlist, is this solution involving DP? great explanation btw this is the only video regarding this problem i could understand
the solution isn't dp but you can solve it with dp approach. But, I don't think you can pass all the test with dp because of Exceed Time Limited, my dp approach only passed 147 / 180
@@minh1391993 care to explain how you used dp for this,
Perfect. Thank you!
I tried so hard with recursive calls and cache, thank you for the explanation! I wonder why I never come up with that clever idea though. I thought about expanding out from the center, but I was trying to find "the center (of answer)" and expand out only once.
i like your username
@@aat501 Thank you! And my cousin Lobstero should feel equally flattered :)
Are you referring to 1 and 2 element when you said odd and even length?
Very good solution.
If you add at the beginning of for loop the line "if resLen > 0 and len(s) - i - 1 < resLen // 2 : break" you will speed up the algorithm faster than 90 % submissions and get a runtime of about 730 ms. The idea is if you already have the palindrome you don't have to loop till the end of "s". You can break the loop after the distance till the end of "s" is less than resLen / 2.
This helped me avoid TLE in leetcode.
But what if after looping till the end, the palindrome is of bigger length?
Братан, хорош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще?
I didn't get the part where you say that you would be starting from the mid position and will travel both sides i.e left and right but you also start your pointers from the starting point i.e 0. Could you please explain how exactly this works? I have watched your video thrice but cannot understand how exactly it is working. I want to understand where is the mid point because since l pointer is already 0 it would keep decrementing i.e -1. That is what I am able to understand.
Thanks for the content. What keyboard do you use?
I used to have a mechanical one, but now I use and prefer this really cheap logitech keyboard: amzn.to/3zQBozP
May I ask why should we expand the l and r outward?
your solutions are easier than the one on leetcode premium. smh. Thanks a lot! may god bless you!
i dont think i have a seen easier way to get this .. i always struggle with the dp 2d array and make mistake .. thanks for making it clear 👍🏻
What's the complexity evaluation for this solution?
# 5. Longest Palindromic Substring
def longestPalindrome(self, s: str) -> str:
res = ""
resLen = 0
start, end = 0, 0
# algo - O(n^2) - starting from the at the chara and expanding outwards
# 2 cases - even and odd len palindrome
for i in range(len(s)):
# odd len
l, r = i, i
# while pointer is still in bound and is a palindrome
while l >=0 and r resLen):
start = l
end = r+1
resLen = r-l+1
l-=1
r+=1
# even len
l, r = i, i+1
while l>=0 and r resLen):
start = l
end = r+1
resLen = r-l+1
l-=1
r+=1
return s[start:end]
# Time: O(n^2)
# Space: O(1)
Bro i have a doubt
l,r= i,i
And after some line of code we write
l,r=i,i+1
So didn't the second l,r will overwrite the first l,r
Since python runs the code line by line so why not this will happen ?
@@HarshKumar-bb9mb correct, the second l,r will overwrite the first l,r
why is this solution considered dynamic programming? i cant see the pattern as dp.
This solution could be further improved using Manacher's algorithm
hi!
can you show manachers O(n) complexity algorithm?
Can someone walk through what the condition if(r-l + 1) is yielding, because when I dryrun it it seems to give 1 for each iteration which would not be greater than resLength. Feeling a little confused as to how this line of code plays out in real time
You saved my day :D, thanks.
Great explanation !!
Thanks for giving the bit of insight to your struggles...lets us know your human ;)
How can you tell O(N^2) is the best possible complexity?
why this is labelled as a dp problem? I used dp method and got timeout since its n^3
Awesome content!! Kudos :)
i get the code for the odd, but not that even. how does adding 1 to the right pointer make it solvable for even length stirng?
NC is checking the case where the palindromic substring is of even number in character length. In order to check that, you need to have p1 pointing to i and p2 pointing to i + 1. p2 can be i -1. It depends how you want to solve the problem.
For example, say we have abba.
In order to spot, "abba", you need p1 = 1 and p2 = 1 + 1 = 2.
You can't get abba, if both of your pointers, p1 and p2 are 1.
anyone can help explain why the solution were able to tell if s is even number or odd number length? i was thinking we needed to check that with modulus. thanks
Same doubt. What about complexity you think its n2? Imo it should be n3
Your explanations to the hard problems are the best.
how is it being checked whether it's an odd length or even length string? Loved your video btw!
it's quite simple it you draw a square matrix of cases where rows and cols are each character of string.
for the first case where your final answer is a palidrome with odd length, you alway start from the diagonal line of the matrix and expand around the center in the same speed. that's why l and r are set to the same index
for the second case where your palindrome is even length, you would start from two points along the diagonal but now two parallel lines then start expand the same
@@minh1391993 I appreciate your efforts but I am new to dp and it's getting hard for me to visualize
I calculate time complexity of your brute force solution as N Factorial - 1. "babad" 5 + 4 + 3 + 2.
That's not factorial, factorial would be 5 * 4 * 3 * 2...etc. It's quadratic because the sum of the natural numbers up to N is O(N^2).
Great explanation