# 5. Longest Palindromic Substring

See question at [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)

### Solution

LeetCode solution: <https://leetcode.com/problems/longest-palindromic-substring/solution/>

### My attempt

I didn't know how to do this one. I tried brute force to start, whereby I was comparing the first letter with the last and then moving the pointers. This didn't work and I ended up with multiple loops.

I googled and found the "[Expand around the center](/cs-theory-and-problems/algorithms/sliding-window.md#expand-around-the-center)" technique for determining palindromes. One way to find palindromes is to compare the first letter to the last letter, the second letter to the 2nd to last letter and so on. The other way is the "[Expand around the center](/cs-theory-and-problems/algorithms/sliding-window.md#expand-around-the-center)" technique.

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s
        # I stored the palindrome itself. Leetcode had an alternate solution where they store the position and
        # max length of the anagram. At the end they return the substring based on that position and length.
        # That approach is faster than my approach below as I'm getting the substring from each call to the
        # expand_around_center function. And then I'm checking lengths on the substring. Just checking the maths
        # is faster. This still works though.
        longest_palindrome = s[0]
        for i in range(len(s)):
            # find for odd sized, where the center is one character: "aba"
            palindrome_odd = self.expand_around_center(s, i, i)
            # find for even sized, where center is two characters: "abba"
            palindrome_even = self.expand_around_center(s, i, i + 1)
            temp_palindrome = palindrome_odd if len(palindrome_odd) > len(palindrome_even) else palindrome_even
            longest_palindrome = longest_palindrome if len(longest_palindrome) >= len(temp_palindrome) \
                else temp_palindrome
        return longest_palindrome

    def expand_around_center(self, s: str, left: int, right: int) -> str:
        """
        I returned a substring here. An alternative approach is to return the length of the substring
        :param s: the string to search
        :param left: index for left pointer to start at
        :param right: index for right pointer to start at
        :return: The substring
        """
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1: right]
        
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/5.-longest-palindromic-substring.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.