5. Longest Palindromic Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input: s

n ← length(s)
max_len ← 0
rst ← ""
if n is 1:
  return s
for start ← 0 to n - 2
  ends ← all positions whose value is equal to that of start except start index
  for end in ends
    ss = s[start:end + 1]
    if max_len >= length(ss)
      break
    elif ss is palindromic
      max_len ← length(ss)
      rst ← ss
  if start is (n - 1) - max_len
    return rst
return rst

class Solution:
  def longestPalindrome(self, s: str) -> str:
    n = len(s)
    max_len = 0
    rst = ""

    if n is 1:
      return s

    for start in range(n - 1):
      ss = s[start:]
      ends = reversed([end for end in Solution.findAll(ss, start)])
      for end in ends:
        ss = s[start:end + 1]
        if max_len >= len(ss):
          break
        elif ss is ss[::-1]:
          max_len = len(ss)
          rst = ss
      if start is (n - 1) - max_len:
        return rst
    return rst

  def findAll(s, idx):
    e = s[0]
    i = s.find(e)
    while i is not -1:
      yield i + idx  # start is equal to idx
      i = s.find(e, i + 1)