5. 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.

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--，所以需要加回去
    }