Expand way to solve longest palindrome string

Expand way to solve longest palindrome string

Table of contents

No heading

No headings in the article.

Let's continue to talk about the longest palindrome sub string question.The brute force way take has poor performance.

We can consider expanding a specific position from a string to find the longest palindrome sub-string.Look for each character and consider it as the middle of the palindrome string, then expand it from both directions.

For example:

We have a string like "ABABT". we can start from the first character "A", then we find the next one in the right direction is "B", is not match with "A".So we go to the second character "B".

The previous one is "A", and the next one is still "A".So it is matched, the longest sub string can be "ABA" so far.Then left direction is end, and the right direction we can go on.So we should look at the third character as before.

Here is the completed code:

package main

import "fmt"

func spread(s string, left int, right int) string {
    if len(s) == 0 {
        return ""
    }

    // If the string is palindrome string, expand it to both direction
    for left >= 0 && right <= len(s)-1 && s[left] == s[right] {
        left--
        right++
    }

    return s[left+1 : right]

}

func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }

    longestString := string(s[0])
    for i := 0; i < len(s); i++ {
        resOdd := spread(s, i, i)
        resEven := spread(s, i, i+1)

        if len(longestString) < len(resOdd) {
            longestString = resOdd
        }
        if len(longestString) < len(resEven) {
            longestString = resEven
        }
    }

    return longestString
}

func isString()

func main() {
    result := longestPalindrome("ABABCD")
    fmt.Printf("result is %s", result)
}