Задачка литкод python

Question

5. Самая длинная палиндромная подстрока

Учитывая строку s, верните самый длинный 
палиндром

Пример 1: 
 
Ввод: s = &#34;babad&#34;
Выходные данные: &#34;bab&#34; 
Пояснение: &#34;aba&#34; также является допустимым ответом.

Пример 2: 
 
Ввод: s = &#34;cbbd&#34; 
Вывод: &#34;bb&#34;

Андрей · Accepted Answer

Самый тупой из возможных вариантов, рекурсивный перебор всех подстрок: def max_palindrome(s):
  if s == s[::-1]: return s
  return sorted([max_palindrome(s[1:]), max_palindrome(s[:-1])], key=len)[1]

print(max_palindrome(input())) Тоже тупо в лоб, но без рекурсии: def max_palindrome(s):
  res, left = &#34;&#34;, 0
  while left < len(s) - len(res):
      for right in range(left + len(res) + 1, len(s) + 1):
          t = s[left:right]
          if t == t[::-1]:
              res = t
      left += 1
  return res

Алмаз Галиаскаров · Answer

def longest_palindrome(s: str) -> str: 
    if len(s) == 0: 
        return &#34;&#34; 
 
    start, end = 0, 0 
 
    def expand_around_center(left: int, right: int) -> (int, int): 
        while left >= 0 and right < len(s) and s[left] == s[right]: 
            left -= 1 
            right += 1 
        return left + 1, right - 1 
 
    for i in range(len(s)): 
        left1, right1 = expand_around_center(i, i) 
        left2, right2 = expand_around_center(i, i + 1) 
 
        if right1 - left1 > end - start: 
            start, end = left1, right1 
        if right2 - left2 > end - start: 
            start, end = left2, right2 
 
    return s[start:end + 1]

print(longest_palindrome(&#34;babad&#34;))  
print(longest_palindrome(&#34;cbbd&#34;))

Валентин Артамонов · Answer

def longest_palindromic_substring(s): def expand_around_center(left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left + 1:right] if len(s) < 2: return s longest = "" for i in range(len(s)): # Проверяем палиндромы нечетной длины (центр в i) palindrome1 = expand_around_center(i, i) # Проверяем палиндромы четной длины (центр между i и i+1) palindrome2 = expand_around_center(i, i + 1) # Обновляем самый длинный палиндром if len(palindrome1) > len(longest): longest = palindrome1 if len(palindrome2) > len(longest): longest = palindrome2 return longest # Примеры использования print(longest_palindromic_substring("babad")) # Вывод: "bab" или "aba" print(longest_palindromic_substring("cbbd")) # Вывод: "bb"