Skip to content
Advertisement

Palindrome question use of lambda and key

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

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)

User contributions licensed under: CC BY-SA
2 People found this is helpful
Advertisement