5. Longest Palindromic Substring

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

1. Use brute force and a checking method:

//1028 ms    393.9 MB
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if(n <= 1)
            return s;
        for(int l = n; l > 0; l--){
            for(int i = 0; i <= n - l; i++){
                if(s[i] == s[i + l - 1]){
                    if(isPalindrome(s.substr(i, l))){
                        return s.substr(i, l);
                    }
                }
            }
        }
        return "";
    }
private: 
    bool isPalindrome(string s){
        int l = 0;
        int r = s.length() - 1;
        while(l < r){
            if(s[l] != s[r]){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
};

2. Expand around centre

//9 ms    2.7 MB
func longestPalindrome(s string) string {
    if len(s) <= 1{
        return s
    }

    max_length := 1

    l, r, max_l, max_r := 0, 0, 0, 0
    for i := 0; i < len(s); i++{
        //fmt.Println(string(s[i]))

        l, r = extendPalindrome(s, i, i)
        if(r - l + 1) > max_length {
            max_length = r - l + 1
            max_l, max_r = l, r
        }

        l, r = extendPalindrome(s, i, i + 1)
        if(r - l + 1) > max_length {
            max_length = r - l + 1
            max_l, max_r = l, r
        }
    }
    fmt.Println(max_l,max_r)
    return s[max_l:max_r + 1]
}

func extendPalindrome(s string, L int, R int) (int, int) {
    l := L
    r := R
    for(l >= 0 && r < len(s)) {
        //fmt.Println(string(s[l]), string(s[r]))
        //fmt.Println(l,r)
        if (s[l] == s[r]){
            l--
            r++
        } else {
            l++
            r--
            break
        }
    } 

    if (l < 0 || r >=len(s)){
            l++
            r--
    }

    return l, r
}

# 932 ms    13.6 MB

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 1:
            return s

        max_length = 1
        m_l = m_r = l = r = 0

        for i in range(len(s)):
            l, r = self.expandPalindrome(s, i, i)
            if (r - l + 1) > max_length:
                m_l = l
                m_r = r
                max_length = r - l + 1

            l, r = self.expandPalindrome(s, i, i + 1)
            if (r - l + 1) > max_length:
                m_l = l
                m_r = r
                max_length = r - l + 1

        return s[m_l: m_r + 1]



    def expandPalindrome(self, s, l, r):
        while(l >= 0 and r < len(s)):
            if (s[l] == s[r]):
                l = l - 1
                r = r + 1
            else:
                l = l + 1
                r = r - 1
                break

        if(l < 0 or r >= len(s)):
            l = l + 1
            r = r - 1

        return l, r