# 5. Longest Palindromic Substring

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

**Example 1:**

<pre><code><strong>Input: s = "babad"
</strong><strong>Output: "bab"
</strong><strong>Explanation: "aba" is also a valid answer.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "cbbd"
</strong><strong>Output: "bb"
</strong></code></pre>

**Constraints:**

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

***My Solutions:***

从每一个字母或者两个字母的间距之间扩散。

Time: As we are traversing N times (considering each character as center) and for each center we are traversing N length (left and right), total TC will be O(N^2).

```
    public String longestPalindrome(String s) {
        
        String longest = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String sub = expandFromCenter(s, i, i); // 从一个字母中间开始找, e.g.‘aba'
            if (sub.length() > longest.length()) longest = sub;
            sub = expandFromCenter(s, i, i + 1); // 从两个字母中间找, e.g.‘abba’
            if (sub.length() > longest.length()) longest = sub;
        }
        return longest;
    }
    
    public String expandFromCenter(String s, int begin, int end) {
        while (begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
        return s.substring(begin + 1, end); // substring是【），因为之前begin--，所以需要加回去
    }
```