After completing the question on leetcode, I was reviewing other people's solutions and found that this had a crazy fast run time, but I don't fully understand the solution. Was hoping someone could explain it line by line, especially the elif statement.
From what I understand, the first if statement just checks that if you reverse the substring and it matches with the original substring that was reversed, but then I am lost with the elif.
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) <= 1:
return s
i, l = 0, 0
for j in range(len(s)):
if s[j-l: j+1] == s[j-l: j+1][::-1]:
i, l = j-l, l+1
# print(s[i: i+l])
elif j-l > 0 and s[j-l-1: j+1] == s[j-l-1: j+1][::-1]:
i, l = j-l-1, l+2
# print(s[i: i+l])
return s[i: i+l]
Given abcNOONdeRACECAR where | is the loop stepping through the string looking back to see if it's found a longer palindrome, and [] is around the best known palindrome, and the number is the length of the best known so far, it does this:
a|bcNOONdeRACECAR [a]bcNOONdeRACECAR 1
ab|cNOONdeRACECAR [a]bcNOONdeRACECAR 1
abc|NOONdeRACECAR [a]bcNOONdeRACECAR 1
abcN|OONdeRACECAR [a]bcNOONdeRACECAR 1
abcNO|ONdeRACECAR [a]bcNOONdeRACECAR 1
abcNOO|NdeRACECAR abcN[OO]NdeRACECAR 2
abcNOON|deRACECAR abc[NOON]deRACECAR 4
abcNOONd|eRACECAR abc[NOON]deRACECAR 4
abcNOONde|RACECAR abc[NOON]deRACECAR 4
abcNOONdeR|ACECAR abc[NOON]deRACECAR 4
abcNOONdeRA|CECAR abc[NOON]deRACECAR 4
abcNOONdeRAC|ECAR abc[NOON]deRACECAR 4
abcNOONdeRACE|CAR abc[NOON]deRACECAR 4
abcNOONdeRACEC|AR abc[NOON]deRACECAR 4
abcNOONdeRACECA|R abcNOONdeR[ACECA]R 5
abcNOONdeRACECAR| abcNOONde[RACECAR] 7
RACECAR
(I think the most benefit comes from the effort of trying to puzzle it out for oneself).
Things I note:
return s[i: i+l] so i must become the start of the palindrome substring and l must become its length.for j in range(len(s)) j steps through the string from left to right and does not go backwards; this code finds the answer in one-pass over the string.if/elif which means there's a missing else which is where "I have not found a palindrome right now, do nothing" happens.else and printing in there might help."gg", "toot" or odd length "a", "lol", "racecar". You can increase the length of a palindrome by +1 or +2. The if and elif are these cases, add one to the right and see if it's a longer palindrome, add one to the left and one to the right and see if it's a longer palindrome.j-l a lot, which we see is the current position in the string, minus the length of the best known palindrome. i.e. the index j is considered to be *at the end of the possible palindrome, looking backwards.Starting at the beginning s[j-l: j+1] is 0-0 to 0+1 which is the first character. One character is a palindrome, so start and length are updated i, l = j-l, l+1 this is now the best known candidate.
j moves on to index 1. Now the test s[j-l: j+1] is asking "looking back from this position, the length of the best known palindrome and one-char forward, is there a 2 character palindrome ending at the second character?".
The elif test s[j-l-1: j+1] looks back one character further, as long as that doesn't go back past the beginning of the string, j-l > 0.
If it finds that it's on the end of a longer palindrome than the best known, it updates start i and length l to be the current one.
Otherwise, j moves on one char into the string. As j moves one further, the palindrome can only grow by length 1 or 2, it can't go +5 in one move. So either the palindrome grows +1 palindrome or +2, or we've moved past a palindrome and out into unknown territory. In unknown territory we're only looking for longer palindromes than the best known, not starting from 1 again.