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!

CodePudding user response：

currentLongest = [0, 1], this is the initial assumption. in this code assume that the longest palindromic substring is a string which start from 0 and end from 1.

for example:

if given string is abcdc it assume currentLongest as a (from index 0 to 1).

Then in the for loop in longestPalindromicSubstring function, it checks and increases the index by one. in even, and odd cases. it gets even length and odd length substrings to check. You can check the length by the values that pass into getLongestPalidromeFrom function. ( (i-1),(i),(i 1) length= 3 odd ).

in getLongestPalidromeFrom function it increases length by two and checks is it palindromic or not. then return the longest palindromic sub string that can generate by starting given points .

in longest it checks what is the longest substring from odd and even length strings. and then in currentLongest it compares the new longest value with the previous longest (cuurentLongest) value.

Remember indexes in currentLongest, longest are the indexes of starting and endpoints of the sub-string. So length equal to x[1]-x[0]. the lambda function.

there can be some mistakes in indexing in my explanation. but totally idea is this.

CodePudding user response：

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

CodePudding user response：

After some guessing, I think I figure this out, and would suggest that you try the following code to see if that can help you understand the posted code better: [Notes] this is not direct answer, rather try to demystify the alternative to solve this problem, or as a reference.

def longestPalindromeSub(string):
    N = len(string)
    for i in range(N)[::-1]:
        for idx in range(N-i):
            word = string[idx: idx i 1]
            if word == word[::-1]:     # palindrome is symmetric 
               return word
    return ''  # not found

Running with word = 'racecar'

>>> print(longestPalindromeSub(word))
    `racecar`

>>> print(longestPalindromeSub('mississippi'))
    'ississi'