Find longest Palindromic substring

Question

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
```

Answer 1

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

Answer 2

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.