I tried to solve it using recursion. Here's my code. It is failing for "ABDA" (returning 3 instead of 1). The reasoning for this is clear to me but I'm not sure how to fix that.
def lps(s):
print(s)
n = len(s)
if n <= 1:
return n
if s[0] == s[n-1]:
return 2 + lps(s[1:-1])
return max(lps(s[:-1]), lps(s[1:]))
The question missed some information to know exactly what you are looking for. I'll assume in the following that you want to find the longest prefix that is also a suffix (in reverse order).
Recursively, the idea is to compare the first and the last characters. If they are not equal, then it cannot be a palindrom (in that case, return 0). If they are equal, the length of that "palindromic part" is 1 + the length of the "palindromic part" of the remaining word (ie. the word without its first and last characters):
def lps(word):
if len(word) > 0 and word[0] == word[-1]:
return 1 + lps(word[1:-1])
else:
return 0
print(lps('abc'))
print(lps('abca'))
print(lps('abba'))
print(lps('abcba'))
print(lps('abda'))
results in 0, 1, 2, 3, 1.
These numbers represent the longest prefix that is (in reverse order) also a suffix.
As you can see, "abba" leads to a length of 2 (because of "ab"), even if its a palindrom of length 4. If you want to get the total length of that palindrom, it's probably easier to do it iteratively:
def lps_full(word):
i = len(word)
while i > 0:
if word[:i] == word[:-i-1:-1]:
return i
i -= 1
return 0
The same examples lead to 0, 1, 4, 5, 1, ie., the same results than above for words that are not palindrom, and the length of the word for words that are.
The same function can be defined recursively if it's mandatory for you:
def lps(word, i=0):
if len(word) > i and word[i] == word[-i-1]:
return lps(word, i+1)
else:
return i