Tap to unmute

Longest Palindromic Substring - Python - Leetcode 5

  Рет қаралды 586,881

NeetCode

NeetCode

Күн бұрын

Пікірлер: 445
@NeetCode
@NeetCode 4 жыл бұрын
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
@serioussam2071
@serioussam2071 Жыл бұрын
@NeetCode make a video on Manachar's algo. I couldn't wrap my head around it
@devonfulcher
@devonfulcher 4 жыл бұрын
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].
@NeetCode
@NeetCode 4 жыл бұрын
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.
@shivakumart7269
@shivakumart7269 3 жыл бұрын
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
@devonfulcher
@devonfulcher 3 жыл бұрын
@@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.
@shivakumart7269
@shivakumart7269 3 жыл бұрын
@@devonfulcher It says, topic does not exist
@beary58
@beary58 3 жыл бұрын
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.
@rishabhjain4546
@rishabhjain4546 3 жыл бұрын
I looked at solutions from other people, but your explanation was the. best. In 8 mins, you explained a 30 min solution.
@mostinho7
@mostinho7 Жыл бұрын
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
@thezendawg
@thezendawg Жыл бұрын
This can be solved with dp though
@samuraijosh1595
@samuraijosh1595 Жыл бұрын
@@thezendawgeven faster?
@satyamkumarjha8152
@satyamkumarjha8152 Жыл бұрын
@@samuraijosh1595 yes,the solution proposed in this video takes n^3 time complexity whereas the solution using dp takes only n^2
@EE12345
@EE12345 9 ай бұрын
@@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
@yassermorsy8481
@yassermorsy8481 3 ай бұрын
It can be solved with DP, but it would be 2D DP I think
@chehakmalhotra7807
@chehakmalhotra7807 Жыл бұрын
Why's this under the 1-D DP tag
@derek_chi
@derek_chi 3 жыл бұрын
Love your vids. I swear you're the best leetcode tutorial out there. You get to the point and are easy to understand.
@mike19558
@mike19558 3 жыл бұрын
It's also super useful that he explains the time complexity of the solutions.
@littlebox4328
@littlebox4328 3 жыл бұрын
man I have the exact feeling!!!
@mama1990ish
@mama1990ish 3 жыл бұрын
I only check this one channel for all questions
@navadeepiitbhilai9470
@navadeepiitbhilai9470 Жыл бұрын
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; } };
@AbdulWahab-jl4un
@AbdulWahab-jl4un 6 ай бұрын
U are a true genius. Great Explanation because no else in entire youtube has explained it better than you.
@jacqueline1874
@jacqueline1874 4 жыл бұрын
you're my leetcode savior!
@NeetCode
@NeetCode 4 жыл бұрын
Haha I appreciate it 😊
@doodle_pug
@doodle_pug 4 жыл бұрын
I've been scratching my head on this problem for a few days thank you for your clean explanation and video!
@jeevanel44
@jeevanel44 2 жыл бұрын
Thanks!
@NeetCode
@NeetCode 2 жыл бұрын
Thank you so much!!!
@sowbaranikab1302
@sowbaranikab1302 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)]:
@enriqeu23452
@enriqeu23452 Жыл бұрын
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).
@shakthi6351
@shakthi6351 Жыл бұрын
Thanks, this is what i came for.
@nagame859
@nagame859 2 ай бұрын
Great🙌👏 But I believe sir's sol is the most optimal in terms of both time and memory.
@symbol767
@symbol767 2 жыл бұрын
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.
@davidespinosa1910
@davidespinosa1910 10 ай бұрын
The Neetcode Practice page lists this problem as 1-D Dynamic Programming. The solution in this video is perfectly fine. But *it doesn't use DP* . This video: O(n^2) time, O(1) space 1-D DP: O(n) time, O(n) space.
@o3_v3
@o3_v3 8 ай бұрын
I'm glad to see that I'm not the only one confused here.
@FirstnameLastname-rm2qi
@FirstnameLastname-rm2qi 5 ай бұрын
@@o3_v3 it is it has O(1) memory, and dp has O(n) memory
@chihoang910
@chihoang910 4 ай бұрын
I believe his expanding mid solution is easier to come up with in an interview and uses constant memory. AFAIK the dp solution is O(n^2) time and space. Do you have an implementation for O(n)?
@davidespinosa1910
@davidespinosa1910 4 ай бұрын
@@chihoang910 No, I don't know an O(n) solution. If anyone has one, please let us know. 🙂 (Also, I updated my comment. TLDR: the solution in the video isn't DP.)
@arpitjaiswal5972
@arpitjaiswal5972 2 ай бұрын
@@davidespinosa1910 Manacher's Algorithm
@rodrigoferrari8314
@rodrigoferrari8314 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.
@IsomerMashups
@IsomerMashups 3 жыл бұрын
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.
@freyappari
@freyappari Жыл бұрын
Simplest solution: def longestPalindrome(self, s: str) -> str: longest = "" for i in range(len(s)): # checking for even and odd strings for r_off in range(2): r, l = i + r_off, i while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1 r += 1 longest = max(longest, s[l + 1 : r], key=len) return longest
@illu1na
@illu1na Жыл бұрын
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
@gradientO
@gradientO Жыл бұрын
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]
@yilmazbingol4838
@yilmazbingol4838 3 жыл бұрын
Why is this considered to be a dynamic programming example?
@anishkarthik4309
@anishkarthik4309 Жыл бұрын
It is
@judahb3ar
@judahb3ar Жыл бұрын
Great question, I’m wondering the same
@hasansihab3555
@hasansihab3555 Жыл бұрын
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
@Briansilasluke
@Briansilasluke Жыл бұрын
This solution is without dp, it can be solved with dp too but this isn’t it
@Dermotten
@Dermotten 10 ай бұрын
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).
@Mohib3
@Mohib3 3 жыл бұрын
You are the GOAT. Any leetcode problem I come here and 95% of time understand it
@uditisinha357
@uditisinha357 3 ай бұрын
Usually I would complain about typing out the exact same code again instead of just copy-pasting it, but the keyboard sounds were satisfying af so I can't complain
@federicoestape4111
@federicoestape4111 3 жыл бұрын
This was definitely the best way to finish my day, with an AWESOME explanation
@victorvelmakin9907
@victorvelmakin9907 3 жыл бұрын
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.
@bidishadas832
@bidishadas832 2 жыл бұрын
This helped me avoid TLE in leetcode.
@krishnanspace
@krishnanspace Жыл бұрын
But what if after looping till the end, the palindrome is of bigger length?
@ErinTiha
@ErinTiha Жыл бұрын
why is there no check to see if the length is odd or even? because otherwise the code would go through both while loops right? That part is a little confusing
@krishnanspace
@krishnanspace Жыл бұрын
Thats what I was thinking. The string is either even length or odd length. There should have been an if condition, otherwise it would compute it additionally
@youngjun916
@youngjun916 6 ай бұрын
I did that and it didn't work. For example: s = "ab" This has an even length so we put l, r = i, i + 1. But since s[0] != s[1], it won't even pass the if condition in the while loop and return "". The expected output should be "a" as a single character also counts as a palindromic substring. Hence, not checking if the length is odd or even allows our program to go into both while loops wherein l, r = i, i in another while loop. This will work as s[0] == s[0]. Hence the res gets updated to "a" and matches the expected output.
@SreedevPS
@SreedevPS 5 ай бұрын
At a time we need to check both scenarios one after another. not only one scenario at a time.
@amanladla6675
@amanladla6675 8 ай бұрын
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?
@Lucas-01922
@Lucas-01922 8 ай бұрын
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).
@matthewsarsam8920
@matthewsarsam8920 2 жыл бұрын
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!
@arnabpersonal6729
@arnabpersonal6729 3 жыл бұрын
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
@inikotoran
@inikotoran 3 жыл бұрын
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!
@AliMalik-yt5ex
@AliMalik-yt5ex 2 жыл бұрын
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.
@ShibirBasak
@ShibirBasak Жыл бұрын
Says, "we can write a function .. but I am lazy to do that". However, types the whole thing again instead of Ctrl + c, Ctrl +v. Respect !!
@_ipsissimus_
@_ipsissimus_ 3 жыл бұрын
an actual beast. i had to look up the list slicing because i thought the [:stop:] value was inclusive. thanks for the great content
@mehmetnadi8930
@mehmetnadi8930 2 жыл бұрын
thanks for being honest and telling us that it took you a while to figure this out. It is empowering ngl
@Dhruvbala
@Dhruvbala 7 ай бұрын
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.
@rploeger
@rploeger 3 ай бұрын
I solved this with a sliding window, starting with a window of the entire array. Every time the window passes over, the size decreases by one. For every iteration you can check from the outside inward if the characters are equal. Pretty sure this is also O(n^2) class Solution: def longestPalindrome(self, s: str) -> str: def isPali(l, r): while l < r: if s[l] != s[r]: return False l, r = l+1, r-1 return True l, r = 0, len(s)-1 while l < r: if isPali(l,r): return s[l:r+1] l, r = l+1, r+1 if r == len(s): r = r-l-1 l = 0 return s[0]
@gordonlim2322
@gordonlim2322 2 жыл бұрын
Could you explain why this is a dynamic programming problem? How would you draw a decision tree for this as you did for other dynamic programming programs like House Robber?
@NeetCode
@NeetCode 2 жыл бұрын
This problem is a bit different, since there isn't a very useful recursion/memorization solution. While this problem does have sub problems, they don't need to be stored in memory. It still has some DP aspects to it imo tho.
@gordonlim2322
@gordonlim2322 2 жыл бұрын
@@NeetCodeThank you for the reply. I just read the LeetCode solutions and saw that they cached if an inner substring is a palindrome and if it was just check the first and last letters. And then they improved to your solution to save memory. In that case, should knowing that this problem is a dynamic programing problem help me solve this? I am just wondering if I should be able to generalize to other dynamic programming problems if I knew how to do House Robber, Longest Palindrome etc. since every question can be different? Cause right now I feel like for the same topic of interview question, different problems might seem like they have similar ideas but have totally different approaches. How will I ever be ready to solve an unseen interview question then? I hope you could guide my mindset in the right direction. Thank you.
@christineeee96
@christineeee96 2 жыл бұрын
how does it know it begins at middle?
@vishetube
@vishetube Жыл бұрын
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?
@diludhillonz
@diludhillonz 3 жыл бұрын
Great explanation. I was struggling with this one even after looking at answers.
@supremoluminary
@supremoluminary Жыл бұрын
I haven’t figured out the right way to solve this. Your approach starts from the left to see if the first character is the longest palindromic substring, then increments one character at a time until getting through the entire string. Why not start from the middle? Isn’t that the best case?
@piyushupadhyay8361
@piyushupadhyay8361 2 жыл бұрын
simplicity * 100 at 7:36 he mention , it took a while for him, gives a sense of relief.....kind of you be motivating us....thanks Neetcode
@marvinxu2950
@marvinxu2950 2 жыл бұрын
I've watched several video solution on this problem and yours is the easiest to understand. Thanks a lot!
@Obligedcartoon
@Obligedcartoon 3 жыл бұрын
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.
@meeradad
@meeradad 10 ай бұрын
Love the solution. I was wondering why this is under a "dynamic programming" category. I thought that dynamic programming should have some version of updating one or more values in one iteration that are then used in some other iteration. Having found a longest palindromic string upto a value of the center index, we do not seem to have a reason for using that information at another value of a center index.
@Angx_only
@Angx_only Жыл бұрын
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.
@SreedevPS
@SreedevPS 5 ай бұрын
No.. its working don't try to add extra code for checking is it odd or even.. first i got the same issue and after the debug i removed the odd or even check and got the answer
@aptus716
@aptus716 2 жыл бұрын
6:46 "Maybe we can use a function but I'm too lazy to do that" Proceeds to write the entire code again instead of copy pasting.
@Bamboo_gong
@Bamboo_gong 2 жыл бұрын
why is this solution considered dynamic programming? i cant see the pattern as dp.
@brandonwie4173
@brandonwie4173 3 жыл бұрын
Just like another guy said, his explanation is well packed, straight to the point. Please keep up the good work. 🔥🔥🔥
@PippyPappyPatterson
@PippyPappyPatterson 2 жыл бұрын
What's the complexity evaluation for this solution?
@hwang1607
@hwang1607 Жыл бұрын
Same solution but using a function to make it less code: You can make the variables global or make them lists if you dont want to use nonlocal class Solution: def longestPalindrome(self, s: str) -> str: res = "" reslen = 0 def check(l,r): nonlocal reslen nonlocal res while l >= 0 and r < len(s) and s[l] == s[r]: if (r - l + 1) > reslen: reslen = (r - l + 1) res = s[l:r+1] l -= 1 r += 1 for i in range(len(s)): check(i,i) check(i, i+1) return res
@goldenboy_808
@goldenboy_808 Жыл бұрын
Can you explain the logic for the even use case and setting the pointers to n, and n+ 1 respectively?
@wintersol9921
@wintersol9921 Жыл бұрын
The odd case does not cover any of the possible even cases, so for example lets say the given word is baab: At 1st iteration: we get b, and since left is empty, we get 1 At 2nd iteration: we get a, then left is b, right is a, we get nothing At 3d iteration: again we dont get anything since left is a, right is b So we need the one for the even case, now we can use left and right pointers to get a result of even string. At 1st iteration: We have b and a, On 2nd iteration: We have a and a, so we expand to left and right we get b and b, so we get the longest palindrome. I tried my best to explain, hope it helps.
@ahmetcemek
@ahmetcemek 5 ай бұрын
I write a function to make the code more neet. Here is my solution: class Solution: def longestPalindrome(self, s: str) -> str: res = "" resLen = 0 def isPalindrome(l, r): nonlocal res, resLen while l >= 0 and r < len(s) and s[l] == s[r]: if (r - l + 1) > resLen: res = s[l:r+1] resLen = r - l + 1 l, r = l - 1, r + 1 for i in range(len(s)): # odd length isPalindrome(i, i) # even length isPalindrome(i, i + 1) return res
@Mad7K
@Mad7K 2 жыл бұрын
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.
@biplabsarkar3567
@biplabsarkar3567 Жыл бұрын
Just FYI, you can solve it in O(n) time complexity using Manacher's Algo
@samuraijosh1595
@samuraijosh1595 Жыл бұрын
you cant leave us hanging like that after droppping this bomb. explain how it could be solved in O(n) time.
@JohnWickea
@JohnWickea Жыл бұрын
thank you soo much , i was struggling for a long for this problem . peace finally . Again thanks ❤
@khangmach01
@khangmach01 Жыл бұрын
I see acceptance rate of this question making me nervous, but see your explanation make me feel relieved :)
@gibranmyageri4616
@gibranmyageri4616 Ай бұрын
Hey, can you please make a video on the Manacher's algorithm solution for this problem?
@uditisinha357
@uditisinha357 3 ай бұрын
how would we draw the recursion tree for this? or would there be none for this one?
@Mrkichanpark
@Mrkichanpark 3 жыл бұрын
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?
@JasonKim1
@JasonKim1 3 жыл бұрын
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.
@michaelw8908
@michaelw8908 2 жыл бұрын
Thanks for the great video, but I don't think the logic for checking for palindrome works for the test input "abb", which should output "bb"
@shashankkumar1041
@shashankkumar1041 Жыл бұрын
Yup right
@masc0648
@masc0648 Жыл бұрын
Thank you Neetcode for this video.
@chloe3337
@chloe3337 3 жыл бұрын
# 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)
@HarshKumar-bb9mb
@HarshKumar-bb9mb 2 жыл бұрын
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 ?
@janewu1128
@janewu1128 Жыл бұрын
@@HarshKumar-bb9mb correct, the second l,r will overwrite the first l,r
@matildayipan9004
@matildayipan9004 4 ай бұрын
something I am very confused about is the iteration of i , i is supposed to start from mid point , but with i in range(len(s)) , it is just starting from 0 to the last index .
@shrimpo6416
@shrimpo6416 3 жыл бұрын
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.
@aat501
@aat501 2 жыл бұрын
i like your username
@shrimpo6416
@shrimpo6416 2 жыл бұрын
@@aat501 Thank you! And my cousin Lobstero should feel equally flattered :)
@sauravdeb8236
@sauravdeb8236 3 жыл бұрын
He is giving us quality explanations for free. Hats off. Let me get a job then I will buy you a coffee.
@priyanshuchaurasiya6184
@priyanshuchaurasiya6184 6 ай бұрын
Hi there is a small inefficiency in implementing the solution, in the line you have written: res = s[l:r+1] Slicing is not ofO(1), it takes O(r-l+1) so ultimately your solution will become O(n^3) however you can do it in O(n^2) by just removing the slicing her is the code using the same approach in O(n^2) : *********************************************************** class Solution: def longestPalindrome(self, s: str) -> str: res = "" resLen =0 for i in range(len(s)): #odd len palindrome l,r = i,i temp = "" while l>=0 and r resLen): resLen = r-l+1 res = temp l -= 1 r += 1 #even len palindrome l,r = i,i+1 temp = "" while l>=0 and r resLen): resLen = r-l+1 res = temp l -= 1 r += 1 return res *************************************************
@taran7649
@taran7649 2 жыл бұрын
you set the l,r = i,i how is it middle
@ognjenpingvin
@ognjenpingvin Жыл бұрын
This solution could be further improved using Manacher's algorithm
@stith_pragya
@stith_pragya 10 ай бұрын
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@valiente-w7o
@valiente-w7o Жыл бұрын
Neetcode solution -> n^3 (with method): # Time 0(n^3) # Space 0(1) res = "" def expand(l, r, res): while l >= 0 and r < len(s) and s[l] == s[r]: if (r - l + 1) > len(res): res = s[l:r+1] l -= 1 r += 1 return res for i in range(len(s)): # par lenght: # First Iteration -> Same pos # Second Iteration -> before/after pos res = expand(i, i, res) # even length # First Iteration -> Cur pos + after pos (2 at this time) # Second Iteration -> before/after pos res = expand(i, i + 1, res) return res Final Solution -> n^2: # Time 0(n^2) # Space 0(1) res = [0, 0] def expand(l, r): while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1 r += 1 return r - l - 1 for i in range(len(s)): # par lenght: # First Iteration -> Same pos # Second Iteration -> before/after pos odd_length = expand(i, i) if odd_length > res[1] - res[0] + 1: dist = odd_length // 2 res = [i - dist, i + dist] # even length # First Iteration -> Cur pos + after pos (2 at this time) # Second Iteration -> before/after pos even_length = expand(i, i + 1) if even_length > res[1] - res[0] + 1: dist = (even_length // 2) - 1 res = [i - dist, i + 1 + dist] l, r = res return s[l:r + 1]
@arpitjaiswal5972
@arpitjaiswal5972 2 ай бұрын
the reason for putting this on blind 75 was to solve in linear time. n^2 is very basic question. For linear time -> Manacher's Algorithm
@dbappz8293
@dbappz8293 9 ай бұрын
damn i need more than 1 days to solve it with brute force technique, and when you said we can check it from the middle and will save so much time, i think... amazing you're right, how can im not thinking about that..
@rotichbill637
@rotichbill637 3 жыл бұрын
This content is way better than LeetCode premium
@frzhouu2676
@frzhouu2676 2 жыл бұрын
Such amazing code. I have same idea as yours but unable to write such a concise code. AWESOME
@sulavasingha
@sulavasingha Жыл бұрын
One of the best explaination so far
@alexandersmirnov4274
@alexandersmirnov4274 2 жыл бұрын
hi! can you show manachers O(n) complexity algorithm?
@supercarpro
@supercarpro 2 жыл бұрын
thanks neetcode you're out here doing holy work
@delsix1222
@delsix1222 9 ай бұрын
why do we start at middle? what if the string was for example "adccdeaba"? The longest palindrom here is "aba", but wouldn't your code give "d" instead, because it is the only case that'd work with s[l] == s[r]? i don't understand what am I missunderstanding
@aniketsinha2826
@aniketsinha2826 2 жыл бұрын
i don't know ...how i will thanks to you for such wonderful videos !! appreciated
@mengyunyi1835
@mengyunyi1835 2 жыл бұрын
May I ask why should we expand the l and r outward?
@jacobli2676
@jacobli2676 4 ай бұрын
Hi, the space complexity of your solution to me seems like O(1) as no extra space is not required but the input. Can you elaborate on this?
@porassingh4904
@porassingh4904 3 жыл бұрын
how is it being checked whether it's an odd length or even length string? Loved your video btw!
@minh1391993
@minh1391993 3 жыл бұрын
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
@porassingh4904
@porassingh4904 3 жыл бұрын
@@minh1391993 I appreciate your efforts but I am new to dp and it's getting hard for me to visualize
@amandatao9622
@amandatao9622 3 жыл бұрын
Your explanation saved my life!!! Thank youuuu! I like how you explain you look at this question.
@calvinlai3354
@calvinlai3354 4 жыл бұрын
really enjoy your content, super informative! keep them coming
@anujapuranik2000
@anujapuranik2000 Жыл бұрын
@neetcode - a Quick Question --- where is the variable resLen being used? I meant I didnt see it contributing to the final res string..
@aditdesai5138
@aditdesai5138 9 ай бұрын
Its used as a decider for next iteration whether or not to update the next result
@AramDovlatyan
@AramDovlatyan Жыл бұрын
You tagged this problem as 1D DP in the Neetcode roadmap but the solution you gave is not a DP solution, a rather clever and more performant one but not DP. I think if you are going to use the DP solution, then this problem is better tagged as 2D DP.
@9-1939
@9-1939 4 ай бұрын
Made this very clear and simple Thank you 🔥
@peteremmanuel7578
@peteremmanuel7578 5 ай бұрын
I got placed because of this question, I'll always be grateful to you. Plus I got placed for 7.7 lpa + 10% as a bonus
@peteremmanuel7578
@peteremmanuel7578 5 ай бұрын
just stick with what you have, and you'll never regret about what you have. Just trust me on this
@sidforreal
@sidforreal 2 жыл бұрын
Your naive soln actually will be O(n^4) and optimised one will be O(n^3), Need to consider TC that substring will take while copying string
@mojojojo1211
@mojojojo1211 2 жыл бұрын
your solutions are easier than the one on leetcode premium. smh. Thanks a lot! may god bless you!
@gradientO
@gradientO Жыл бұрын
*Here's a Dynamic Programming solution:* dp[i][j] is true if subtring i to j is a plaindrome And here's how to compute it 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])
@DavidDLee
@DavidDLee 2 жыл бұрын
How can you tell O(N^2) is the best possible complexity?
@williambenarto6212
@williambenarto6212 3 жыл бұрын
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
@tejassrivastava6971
@tejassrivastava6971 3 жыл бұрын
Same doubt. What about complexity you think its n2? Imo it should be n3
@JaneDoe-dc2zq
@JaneDoe-dc2zq 3 жыл бұрын
Could someone please explain this to me? @1:45 he says "how many substrings do we actually have to check? n^2". How is it n^2? n^2 is equal to 25 but there are only 15 substrings to check and 15 != 25? Or is this just an approximation? If it's just an approximation, how did he decide on n^2? Thanks!
@sravanikatasani6502
@sravanikatasani6502 3 жыл бұрын
it is approximately n^2 ,its in terms of complexity , to select a substring we need end points right ,among n characters of the string say s , we need to choose 2 characters as endpoints which can be done in nC2 ways i.e n(n-1)/2..and also two end characters can be say same(palindrome of length 1). So in total u can get n(n-1)/2 + n substrings.
@parthib_deb23
@parthib_deb23 9 ай бұрын
can we solve this problem using 3 pointers , where L or left is at 0 , R is at end and M is at middle , either L:R or L:M or M:R will be returned
@supremoluminary
@supremoluminary 4 жыл бұрын
I calculate time complexity of your brute force solution as N Factorial - 1. "babad" 5 + 4 + 3 + 2.
@raymondtan2795
@raymondtan2795 3 жыл бұрын
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).
@avanidixit7181
@avanidixit7181 2 жыл бұрын
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
@MadpolygonDEV
@MadpolygonDEV Жыл бұрын
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
@sangwookim5551
@sangwookim5551 Жыл бұрын
but can you do it in O(n) time?
@netraamrale3850
@netraamrale3850 3 жыл бұрын
Tons of thanks for making these videos. This is really very helpful and video explanation is very nice . optimize and concise
LeetCode 5.  Longest Palindromic Substring (Algorithm Explained)
14:40
Quilt Challenge, No Skills, Just Luck#Funnyfamily #Partygames #Funny
00:32
Family Games Media
Рет қаралды 55 МЛН
IL'HAN - Qalqam | Official Music Video
03:17
Ilhan Ihsanov
Рет қаралды 700 М.
СИНИЙ ИНЕЙ УЖЕ ВЫШЕЛ!❄️
01:01
DO$HIK
Рет қаралды 3,3 МЛН
Palindromic Substrings - Leetcode 647 - Python
15:02
NeetCode
Рет қаралды 166 М.
LeetCode was HARD until I Learned these 15 Patterns
13:00
Ashish Pratap Singh
Рет қаралды 769 М.
Every Minute One Person Is Eliminated
34:46
MrBeast
Рет қаралды 48 МЛН
Longest palindromic substring | Dynamic programming
15:21
Techdose
Рет қаралды 408 М.
LONGEST PALINDROMIC SUBSTRING | LEETCODE # 5 | PYTHON SOLUTION
11:58
Cracking FAANG
Рет қаралды 1,4 М.
Longest Repeating Character Replacement - Leetcode 424 - Python
20:44
How I would learn Leetcode if I could start over
18:03
NeetCodeIO
Рет қаралды 814 М.
Backtracking: Permutations - Leetcode 46 - Python
9:43
NeetCode
Рет қаралды 376 М.
DP 28. Longest Palindromic Subsequence
9:38
take U forward
Рет қаралды 282 М.
Quilt Challenge, No Skills, Just Luck#Funnyfamily #Partygames #Funny
00:32
Family Games Media
Рет қаралды 55 МЛН