Hey guys so I was working on this problem on the algoExpert platform, but I am struggling to understand what longest and currentLongest are really doing.
def longestPalindromicSubstring(string): currentLongest = [0, 1] for i in range(1, len(string)): odd = getLongestPalindromeFrom(string, i - 1, i + 1) even = getLongestPalidromeFrom(string, i - 1, i) longest = max(odd, even, key=lambda x: x[1] - x[0]) currentLongest = max(longest, currentLongest, key=lambda x: x[1] - x[0]) return string[currentLongest[0] : currentLongest[1]] def getLongestPalindromeFrom(string, leftIdx, rightIdx): while leftIdx >= 0 and rightIdx < len(string): if string[leftIdx] != string[rightIdx]: break leftIdx -= 1 rightIdx += 1 return [leftIdx + 1, rightIdx]
Just from the beginning, I am not entirely sure what the currentLongest = [0, 1]
is doing, is it just saying that it will have 2 values?
Are odd and even returning an array of indices?
longest
I know it is taking the max between odd and even, key seems to be taking an **anonymous function lambda ** but I’m not too sure what key does and what x: x[1] – x[0] does. I also don’t understand what currentLongest
is doing with the max. Like what is the purpose of passing longest
and currentLongest
? They are both lists so I am not fully sure what is even going on there. And in the return, if we get something like [3:9]
on longest
, I think all we are doing is slice the string as string(3:9)
but the use of lists is confusing me and the max
and key:lambda
are confusing me more. Any help is appreciated!
Description: Write a function that, given a string, returns its longest palindromic substring. A palindrome is defined as a string that’s written the same forward and backward. Note that single-character strings are palindromes. You can assume that there will only be one longest palindromic substring.
Sample Input:
string = "abaxyzzyxf"
Sample Output:
"xyzzyx"
Thanks to Daniel Hao for asking for more clarifications and thanks to Prasad Darshana for the suggestions on how to better format my code lines. I am new to Stack Overflow so that’s very helpful so I can know how to format and ask better questions next time!
Advertisement
Answer
- Difference between
currentLongest
andlongest
currentLongest
keeps track of the start and end indices of the longest Palindrome it has found so far through iterations. currentLongest
is initialized as currentLongest = [0,1]
, so even if the string is 1 character long, the for loop will not execute and return the single character (via return string[currentLongest[0]:currentLongest[1]]
).
longest
keeps the start and end indices of the longest palindrome found in a single iteration. This is retrieved by performing a lambda operation on 2 arrays: odd and even.
- what x: x[1] – x[0] does?
The lambda operation compares two arrays, odd and even in this way (x denotes each array): It takes each array and subtracts the start index (0) from the end index(1), and outputs the array which has the maximum difference/ distance between start and end indices. (Which indicates the longest substring palindrome)