Longest Palindromic Substring

1. Problem Description

Given a string s, find the longest palindromic substring in s.

2. Approach

• Brute force
• Center expansion

3. Implementation

3.1. Brute Force

func longestPalindrome(s string) string {
	max := 0
	maxStr := ""
	longestPalindrome2(s, 0, len(s)-1, &max, &maxStr)
	return maxStr
}

func longestPalindrome2(s string, left int, right int, max *int, maxStr *string) {
	if left > right {
		return
	}
	if isHuiWen(s, left, right) {
		current := right - left + 1
		if current > *max {
			*max = current
			*maxStr = s[left : right+1]
		}
	} else {
		longestPalindrome2(s, left+1, right, max, maxStr)
		longestPalindrome2(s, left, right-1, max, maxStr)
	}

}

func isHuiWen(str string, left int, right int) bool {
	for left < right {
		if str[left] != str[right] {
			return false
		}
		left++
		right--
	}
	return true
}

3.2. Center Expansion

func longestPalindrome(s string) string {
    res := ""
    runes := []rune(s)
    for i, _ := range runes {
        str := spread(runes, i, i)
        if len(str) > len(res) {
            res = str
        }
        str = spread(runes, i, i+1)
        if len(str) > len(res) {
            res = str
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a 
    }
    return b
}

func spread(runes []rune, left, right int) string {
    for left >= 0 && right < len(runes) {
        if runes[left] == runes[right] {
            left--
            right++
        }else {
            break
        }
    }
    return string(runes[left+1:right])
}

4. References

• 5. Longest Palindromic Substring - LeetCode