Start learning free

LESSON 458 OF 540 · DYNAMIC PROGRAMMING

Longest Palindromic Substring in Go: Expand Around Center in O(n²)

Practice O(n2) Read the full explanation

You are given a string s. Return its longest palindromic substring. If several substrings have that greatest length, return the one that starts first, furthest to the left.

A palindrome reads the same forward and backward, like "racecar" or "abba". A substring is a run of consecutive characters of s: "bcd" is a substring of "abcde", but "ace" is not.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is a palindrome of length 3 too, but "bab" starts first.
No substring of length 4 or 5 is a palindrome.

Example 2:

Input: s = "cbbd"
Output: "bb"
Explanation: A palindrome of even length, like "bb", has its middle between two characters.

Example 3:

Input: s = "abacdfgdcaba"
Output: "aba"
Explanation: "aba" appears at the start and at the end, and the first one is returned.
"abacd" read backward is "dcaba", which also appears in s, but neither of them is a palindrome.

 

Constraints:

  • 1 <= s.length <= 1000
  • s is made of English letters and digits only. Uppercase and lowercase letters are different characters: "Aa" is not a palindrome.

Note:

Your algorithm should run in O(n2) time and use O(1) extra space besides the returned string, where n is the length of s.



Checking every substring on its own takes O(n3): about n2/2 substrings, each up to n characters long. Look at palindromes from the middle instead. Every palindrome has a center: its middle character when its length is odd, or the gap between its two middle characters when the length is even. A string of n characters has 2n - 1 centers: n characters and n - 1 gaps.

From a center, expand: start with two positions left and right (the same character, or two neighbours), and move them one step outward while both are inside s and their characters are equal. When they stop, the palindrome between them has right - left - 1 characters, and it is the longest one around that center. A helper that does this and returns the length, called for the centers (i, i) and (i, i + 1) of every i, finds the longest palindrome at each center.
A palindrome of length length centered at i starts at i - (length - 1) / 2, rounded down. Keep the best start and length, and replace them only by a strictly longer palindrome: the centers go from left to right, so the first of the longest ones stays.

There are 2n - 1 centers, and each expansion takes at most n / 2 steps: O(n2) time. Only a few numbers are kept: O(1) extra space, besides the returned string.
A table dp[i][j] telling whether s[i..j] is a palindrome works too, in the same time but with O(n2) space. Manacher's algorithm even finds the answer in O(n), but it goes beyond this lesson.
STEP 1 OF 13
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Longest Palindromic Substring in Go, explained

    Problem overview

    The function longestPalindrome gets a string s and returns its longest palindromic substring. A palindrome reads the same forward and backward, like "racecar" or "abba". A substring is a run of consecutive characters of s. If several palindromes share the greatest length, the one that starts first, furthest to the left, is returned.

    For "babad" the answer is "bab": "aba" is just as long, but it starts later. For "cbbd" the answer is "bb", a palindrome of even length. For "abacdfgdcaba" it is "aba", the copy at the start. The string holds English letters and digits only, and uppercase and lowercase are different characters, so "Aa" is not a palindrome.

    The lesson asks for O(n²) time and O(1) extra space besides the returned string.

    Approach: grow palindromes from their centers

    Checking every substring one by one costs O(n³): about n²/2 substrings, each up to n characters long. Looking from the middle is cheaper. Every palindrome has a center: its middle character when its length is odd, or the gap between its two middle characters when the length is even. A string of n characters has 2n - 1 centers, n characters and n - 1 gaps.

    From a center, expand. Put two positions, left and right, on the center (the same character, or two neighbours), and move them outward one step at a time while both are inside s and their characters are equal. When they stop, they sit one step beyond the palindrome on each side, so the palindrome has right - left - 1 characters. That is the longest palindrome around that center.

    The main function calls this helper twice for each index i: with (i, i) for an odd center and with (i, i + 1) for the gap after it. It remembers where the best palindrome starts and how long it is, and cuts the substring out once at the end.

    A table dp[i][j] that says whether s[i..j] is a palindrome works too, in the same time but with O(n²) space. Manacher's algorithm finds the answer in O(n), but it goes beyond this lesson.

    Step by step

    1. Keep two numbers: bestStart and bestLen, both 0. They are all you need to remember, and the substring itself is cut out at the end.
    2. Visit every position with a loop of i from 0 while i < len(s). Each i gives two centers: the character s[i] and the gap after it. Together they cover all 2n - 1 real centers, plus an empty gap after the last character.
    3. Call expand(s, i, i) and keep the result in odd. Both ends start on s[i], so this finds the longest odd palindrome centered there. Writing the call before the helper keeps the loop short; the helper comes later.
    4. Call expand(s, i, i+1) and keep the result in even. The ends start on s[i] and s[i+1]. If they differ, or if i is the last index, the length is 0.
    5. Take the larger of odd and even with the built-in max, in length.
    6. Compare with length > bestLen. It is strictly greater: a palindrome as long as the best one starts further right, and the first one must win.
    7. Compute the start as i - (length-1)/2. An odd palindrome has (length - 1) / 2 characters before its middle s[i]. An even one has length / 2 - 1 before its left middle, which is s[i] here. Integer division rounds both to (length - 1) / 2.
    8. Store the new length in bestLen. It is now the palindrome to beat.
    9. Return the slice s[bestStart : bestStart+bestLen].
    10. Write expand below the main function, with parameters s string, left int and right int, returning an int.
    11. Loop while the ends match. The condition is left >= 0 && right < len(s) && s[left] == s[right]: Go's for with only a condition acts as a while.
    12. Move outward: left-- and right++.
    13. Return right - left - 1. The loop stops one step past the palindrome on both sides, so the palindrome runs from left + 1 to right - 1.

    The solution in Go

    func longestPalindrome(s string) string {
    bestStart := 0
    bestLen := 0
    for i := 0; i < len(s); i++ {
        odd := expand(s, i, i)
        even := expand(s, i, i+1)
        length := max(odd, even)
        if length > bestLen {
            bestStart = i - (length-1)/2
            bestLen = length
        }
    }
    return s[bestStart : bestStart+bestLen]
}

func expand(s string, left int, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

    The Go details worth a closer look:

    • Short-circuit order. && stops at the first false check, so s[left] == s[right] is evaluated only when both positions are valid. Indexing outside the string would stop the program with an index-out-of-range panic.
    • Parameters are copies. Go passes ints by value, so left-- and right++ inside expand change nothing in longestPalindrome. That is why the helper returns a length instead of updating the caller's variables.
    • Bytes. s[left] is a byte, and the slice s[a:b] counts bytes. That is fine here, because letters and digits take one byte each. For text with multi-byte characters, you would convert to []rune first.
    • Slices exclude the end. s[bestStart : bestStart+bestLen] takes exactly bestLen bytes.
    • Built-in max. It has been part of the language since Go 1.21.

    Complexity

    Time: O(n²). There are 2n - 1 centers, and each expansion takes at most about n / 2 steps, so the work stays within a constant times n². A string such as "aaaa…a" reaches that limit.

    Space: O(1) extra. Only a few integers are kept. The returned substring shares the memory of s in Go, because slicing a string does not copy it.

    Edge cases and common mistakes

    • Forgetting even palindromes. With only expand(s, i, i), "cbbd" would return "b" instead of "bb".
    • Using >= instead of >. A later palindrome of equal length then replaces the earlier one. For "babad" that version returns "aba" instead of "bab".
    • A string with no repeated characters. For "abc", every palindrome has length 1, and the first one found, "a", stays. The first center always wins on ties, so a one-character result is the first character.
    • Case. "Aa" gives "A", because the two letters are different characters.
    • A wrong start formula. The start for an even palindrome is not i - length/2: for "bb" at i = 1 that would give 0. The expression i - (length-1)/2 gives 1.
    • Single character. "a" gives "a": expand(s, 0, 0) returns 1, and bestLen starts at 0.

    Testing

    For "cbbd", the lengths returned by expand(s, i, i) and expand(s, i, i+1) for each i are:

    i=0: 1 0
i=1: 1 2
i=2: 1 0
i=3: 1 0

    At i = 1 the even expansion returns 2, so length = 2 and the start is 1 - (2-1)/2 = 1, which gives "bb". For "babad" the pairs are 1 0, 3 0, 3 0, 1 0, 1 0. The length 3 first appears at i = 1, so the start is 0 and the answer is "bab"; the length 3 at i = 2 is not strictly greater, so it is ignored.

    More inputs, with the results the function returns:

    • "a" gives "a".
    • "ab" gives "a".
    • "aaaa" gives "aaaa".
    • "abcba" gives "abcba".
    • "forgeeksskeegfor" gives "geeksskeeg".
    • "abacdfgdcaba" gives "aba".
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free