Longest Palindromic Substring - Python - Leetcode 5

0:00 - Conceptual Solution
4:30 - Coding solution

#Coding #CodingInterview #GoogleInterview

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[devonfulcher]

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].

[rishabhjain]

I looked at solutions from other people, but your explanation was the. best. In 8 mins, you explained a 30 min solution.

[mostinho]

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

[derek_chi]

Love your vids. I swear you're the best leetcode tutorial out there. You get to the point and are easy to understand.

[AbdulWahab-jlun]

U are a true genius. Great Explanation because no else in entire youtube has explained it better than you.

[doodle_pug]

I've been scratching my head on this problem for a few days thank you for your clean explanation and video!

[sowbaranikab]

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)]:

[enriqeu]

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
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


# Output: 'anana'
# The time complexity of this solution is O(n^2) and the space complexity is O(n^2).

[davidespinosa]

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.

[symbol]

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.

[Mohib]

You are the GOAT. Any leetcode problem I come here and 95% of time understand it

[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

[uditisinha]

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

[illuna]

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

[victorvelmakin]

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.

[federicoestape]

This was definitely the best way to finish my day, with an AWESOME explanation <3

Thank you and

[rodrigoferrari]

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.

[yilmazbingol]

Why is this considered to be a dynamic programming example?

[IsomerMashups]

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.

[matthewsarsam]

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!