Longest Palindromic Substring

The Idea

Every palindrome has a centre. So try all of them: each character is an odd centre, and each gap between neighbours is an even centre.

From a centre, compare outwards while the two sides match. The moment they differ, that centre is finished — keep the longest stretch you collected.

Real-World Example

Genome tools hunt for reverse-complement palindromes the same way: sit on a position, grow outwards while the pairing holds, stop at the first mismatch. Checking every substring instead would be hopeless on a sequence of millions.

The Code

def longest_pal(s):
    best = ""
    def grow(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left, right = left - 1, right + 1
        return s[left + 1:right]          # last stretch that matched
    for i in range(len(s)):
        for cand in (grow(i, i), grow(i, i + 1)):   # odd and even centres
            if len(cand) > len(best):
                best = cand
    return best

print(longest_pal("babad"))   # bab
print(longest_pal("cbbd"))    # bb

def grow(s, left, right):
  while left >= 0 and right < len(s) and ___:
      left, right = left - 1, right + 1
  return s[left + 1:right]

print(grow("babad", 1, 1))   # want bab