:orphan:

Longest Palindromic Substring
=============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/longest-palindromic-substring/

Given a string ``s``, return *the longest* palindromic substring in
``s``.

 

**Example 1:**

::


   Input: s = "babad"
   Output: "bab"
   Explanation: "aba" is also a valid answer.

**Example 2:**

::


   Input: s = "cbbd"
   Output: "bb"

 

**Constraints:**

- ``1 <= s.length <= 1000``
- ``s`` consist of only digits and English letters.

.. highlight:: python

Pattern
-------
Two Pointers, String, Dynamic Programming

Solution
--------
Any palindromic substring can have odd or even length. If the substring has odd
length, then the center of the palindrome is a single character. If the
substring has even length, then the center of the palindrome are 2 equal
characters. We iterate through ``s`` and find all odd and even centers. Given a
palindromic center, we can expand the substring by moving the start and end
indices while checking that the substring is still a palindrome. When the
palindrome exceeds the previous longest palindrome, replace the longest
plaindrome.

Code
----

.. literalinclude:: ../problems/medium/longest-palindromic-substring/longest_palindromic_substring__approach_1.py
    :language: python
    :lines: 10-

Test
----
>>> from longest_palindromic_substring__approach_1 import longestPalindrome
>>> longestPalindrome('babad')
'bab'
>>> longestPalindrome('cbbd')
'bb'

Complexity
----------
| :math:`n` is the length of the input string
| Time: :math:`O(n^2)` — expand around each character
| Auxiliary Space: :math:`O(1)`

.. autofunction:: longest_palindromic_substring__approach_1.longestPalindrome

.. autofunction:: longest_palindromic_substring__approach_1.longestPalindromeAtCenter

.. autofunction:: longest_palindromic_substring__approach_1.getSubstringBounds