Longest Palindromic Substring

1. The obvious way

   Check every substring to see if it is a palindrome: O(n³).

2. The key insight

   There are 2n-1 centres (n letters and n-1 gaps). From each centre move one step left and one step right while the two letters match; the first mismatch ends that palindrome. Keep the longest. Each expansion costs at most O(n), so O(n²) in total with no extra memory.

3. The algorithm
   1. For every position, spread outwards from that single letter (odd palindromes).
   2. Also spread outwards from the gap between that letter and the next (even palindromes).
   3. Spreading: while the letter on the left equals the letter on the right, step both outwards.
   4. Remember the longest piece found.

Watch it run

longest = "b"

def longest_palindrome(text):
    best = ""

    def spread(left, right):                       # ripple outwards from a centre
        while left >= 0 and right < len(text) and text[left] == text[right]:
            left -= 1
            right += 1
        return text[left + 1 : right]

    for centre in range(len(text)):
        for candidate in (spread(centre, centre), spread(centre, centre + 1)):
            if len(candidate) > len(best):
                best = candidate
    return best

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.