# Find longest Palindromic substring

technical interview question i got from daily interview pro

A palindrome is a sequence of characters that reads the same backwards and forwards. Given a string, s, find the longest palindromic substring in s.

Example:


Input: "banana"
Output: "anana"

Input: "million"
Output: "illi"


i was wondering if there is any way to optimize the code more

Also is using built in functions such as join(),index() and so on not preferred for a coding interview ?Because by using it it makes it so much easier in python compared to languages like java

class Solution:

def checkOddChars(self,lst):
ls = []
for i in lst:
if lst.count(i) == 1:
ls.append(i)
return ls

def checkPalindrome(self,lst):
return lst[:] == lst[::-1]

def longestPalindrome(self, s):
lst = list(s)

while lst:
if self.checkPalindrome(lst) :
return(''.join(lst))

oddChars = self.checkOddChars(lst)

if lst[0] in oddChars:
del lst[0]
if lst[len(lst)-1] in oddChars:
del lst[len(lst)-1]

return('List is empty')

# Test program
s = "tracecars"
print(str(Solution().longestPalindrome(s)))
# racecar
$$$$

• @superbrain What may be "obviously wrong" for you might not be for OP. The point you give is good, but we're trying to convey our messages with a nicer tone :) – IEatBagels Sep 8 '20 at 15:59
• @IEatBagels Alright alright... though I do find it hard to believe that they passed the site's test suite with that. – superb rain Sep 8 '20 at 20:47

Take full advantage of the language. You ask whether one should use handy built-in functions and methods during a coding interview. Absolutely! Interviewers want to see, among other things, that you are fluent in the language(s) where you claim fluency. Write natural, idiomatic code -- not code you think the interviewer wants to see. There can be some pretty big differences of opinion about what constitutes "good" code across different teams and even among interviewers on the same team. Unless they give you specific instructions, write good code as you understand it. And if a team really wants to see Python that looks like Java, perhaps it's not a good fit for you anyway.

No pointless classes. Speaking of which, what is the purpose of Solution? Until the problem calls for a class, don't force one. Just write a ordinary functions. Interviewers can always ask follow-up questions if they want to see you build a class. Again, write natural, readable code to the best of your ability.

Never optimize blindly. You also ask whether there is "any way to optimize the code more". When I interview programmers, one of the key things I want to learn is whether they have common sense. Other than for educational purposes, there's very little to be gained from optimization in the abstract. A person can spend a lot of time and energy optimizing for irrelevant things if they don't appreciate the larger context. Optimization for what -- memory, speed, maintainability? During an interview, never engage optimization discussions without asking clarifying questions: what are the primary goals of the code, how big will the inputs be, how fast does it need to be to keep users happy, and so forth.

Optimize for correctness first. Your current implementation hangs on many input strings (for example, aabb). The problem is that the algorithm has no way to advance when the both the first and last characters in the surviving lst are not singletons. One way or another, lst must change on each iteration under your current design. That suggests that the conditional checks at the end of the while loop take an if-elif-else form. But it's not obvious what to put in the else block. Naively throwing away the first character or the last character will fail (consider inputs like aaabb and aabbb). Perhaps someone smarter than I can repair your current design, but I'm not hopeful.

Develop a habit for testing. You spent a fair bit of effort on your code, but your question lacks evidence of testing. When I'm interviewing someone or developing a new piece of code, I want an easy way to test it out. When working on my computer, I'll use a legitimate testing tool (usually pytest), but when posting an example or question for others, I will often roll the tests into a runnable demo of some kind. For example:

def main():
TESTS = {
'abba': 'abba',
'': None,           # Free thinkers say it should be ''
'x': 'x',
'banana': 'anana',
'tracecars': 'racecar',
'aabbb': 'bbb',
'aaabb': 'aaa',
}
for word, expected in TESTS.items():
got = longest_palindrome(word)
print(got == expected, got, expected)


Classic solutions:

• Brute force with 3 nested loops: O(n^3).
• Dynamic programming using a grid of partial solutions: O(n^2).
• Manacher's Algorithm, which is both clever and a head scratcher: O(n).
• I'll just note that the Solution class is pointless, but it's a requirement for a challenge website (leetcode I believe). – Carcigenicate Sep 7 '20 at 20:11
• Oh no you didn't! Wanted to upvote but then saw you deny the empty string's palindromeness (palindromicness? palindromicity? :-). – superb rain Sep 7 '20 at 20:48
• @superbrain I wondered about that. Is there a World Palindrome Association that rules on such matters? I mean, I taught my child to starting counting from zero, so I'm sympathetic to your cause. – FMc Sep 7 '20 at 21:06
• I actually googled that, didn't find one :-). But it's definitely a palindrome. I'm more certain about that than I am about it not being a cube, and I'm in the World Cube Association. – superb rain Sep 7 '20 at 21:19
• Thanks this helps a lot , I tried adding another function to consider for the inputs that it hangs on but it was getting very lengthy and difficult. I'm Just going to do using the classic solutions u mentioned – Razor Fire Sep 8 '20 at 18:26
def checkPalindrome(self,lst):
return lst[:] == lst[::-1]


This is an extremely expensive implementation. lst[:] is needlessly creating a copy of lst, then lst[::-1] creates a second complete copy of lst (but reversed). There are many ways of approaching this, but I would go for something like this:

def checkPalindrome(self, lst):
return all(start == end
for start, end in zip(lst, reversed(lst)))


It zips lst with a reversed list iterator:

>>> lst = "abcd"
>>> list(zip(lst, reversed(lst)))
[('a', 'd'), ('b', 'c'), ('c', 'b'), ('d', 'a')]


Then checks to see if all the pairs are equal. If they are, the list is a palindrome. This method is still inefficient though since only half of each needs to be checked. It can be further improved by introducing itertools.islice to get a "view" of the first half of the zipped lists:

from itertools import islice

def checkPalindrome(self, lst):
half_pair_view = islice(zip(lst, reversed(lst)), len(lst) // 2 + 1)
return all(start == end for start, end in half_pair_view)


islice is like normal list slicing except instead of creating a copy, it just allows you to iterate over a limited portion of the original iterable.

This code is more efficient because every function involved here is "lazy": they do only as much work as they need to. reversed, zip, islice, and the generator expression all return an iterator that can produce elements (but do little work up front). all also exits as soon as it gets a Falsey result, so it's comparable to a for loop that contains a break in some branches. This is key here because we only want to do as much work as is necessary to determine whether not they're palindromes. Making two full copies of the list does a large amount of work; far more than is required to check if the string is a palindrome.

checkOddChars is a textbook use-case for a list comprehension:

def checkOddChars(self, lst):
return [i for i in lst if lst.count(i) == 1]


If you ever find yourself initializing an empty list, then iterating over another iterable and adding to the list, you likely want a comprehension.

This is quite an expensive function too. count needs to iterate the entire list each time; once for every element in lst. This also double counts any repeated elements. I'm not sure off the top of my head what a better solution is though.

 del lst[0]


This is also quite expensive. Ideally, you shouldn't delete from a list except for at the very end. Lists don't support efficient deletes, and the closer to the beginning of the list you delete from, the worse it is. I'd switch to using a dequeue instead of a list, which avoids the overhead of popping from the beginning.

• You appear to be a bot :-). Suggesting mechanical improvements but not realizing that their solution is wrong, not even that == 1 doesn't check oddness... – superb rain Sep 7 '20 at 19:42
• @superbrain I admit, I didn't check correctness. For most reviews I do, I simply scan over the code and when something jumps out at me, I make note of it. If I need to dig into functionality to suggest an improvement, I do to the extent that's necessary. So yes, I did do this review as a context-less bot would. – Carcigenicate Sep 7 '20 at 19:43
• By "odd chars" though, I figured that was just weird phrasing, and that a character is considered to be "odd" (not in the numerical sense) if it's only in the string once. – Carcigenicate Sep 7 '20 at 19:45
• Btw, I'd mention that all stops early if it can. That's rather crucial. If it didn't, then I'm pretty confident that lst == lst[::-1] would be faster. Especially if they did it with a string instead of a list. – superb rain Sep 7 '20 at 19:45
• Ah, ok. That kind of oddness. If that were the case, if lst[0] not in lst[1:]: might be good. Or if lst.count(lst[0]) == 1:` – superb rain Sep 7 '20 at 19:48