← Back to DevBytes
Go August 06, 2026 12 min read

Solving Longest Palindromic Substring in Go: Step-by-Step Guide

Introduction to the Longest Palindromic Substring Problem

The Longest Palindromic Substring problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. Given a string s, the task is to find the longest contiguous substring that reads the same forwards and backwards. For example, in the string "babad", both "bab" and "aba" are valid answers, each with a length of three.

While the problem statement is deceptively simple, the challenge lies in solving it efficiently. A naive approach can take cubic time, but with the right technique, you can reduce this to linear time. In this tutorial, we will explore multiple approaches to solving this problem in Go, starting from the brute force method and progressing to the optimal Manacher's algorithm.

Why This Problem Matters

Beyond being a frequent interview question at companies like Amazon, Google, and Microsoft, the Longest Palindromic Substring problem teaches several fundamental concepts that every developer should master:

Understanding this problem deeply will make you a stronger problem solver and give you tools that transfer to many other algorithmic challenges.

Understanding Palindromes

Before diving into code, let us clarify what a palindrome is. A palindrome is a sequence of characters that reads identically from left to right and right to left. Palindromes come in two flavors that matter for this problem:

This distinction is crucial because any algorithm that expands around a center must handle both cases. Failing to account for even-length palindromes is one of the most common bugs developers introduce when first attempting this problem.

Approach 1: Brute Force

The most straightforward approach is to generate every possible substring and check whether each one is a palindrome. While this is easy to understand and implement, it is computationally expensive.

How It Works

For a string of length n, there are approximately n² substrings. For each substring, checking whether it is a palindrome takes O(n) time in the worst case. This gives us an overall time complexity of O(n³), which is impractical for strings longer than a few hundred characters.

Implementation

package main

import "fmt"

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

func longestPalindromeBruteForce(s string) string {
    if len(s) < 2 {
        return s
    }

    longest := ""
    for i := 0; i < len(s); i++ {
        for j := i; j < len(s); j++ {
            if isPalindrome(s, i, j) {
                if j-i+1 > len(longest) {
                    longest = s[i : j+1]
                }
            }
        }
    }
    return longest
}

func main() {
    testCases := []string{"babad", "cbbd", "a", "ac", "racecar"}
    for _, tc := range testCases {
        fmt.Printf("Input: %s -> Longest Palindrome: %s\n", tc, longestPalindromeBruteForce(tc))
    }
}

When you run this code, you will see output like:

Input: babad -> Longest Palindrome: bab
Input: cbbd -> Longest Palindrome: bb
Input: a -> Longest Palindrome: a
Input: ac -> Longest Palindrome: a
Input: racecar -> Longest Palindrome: racecar

The brute force approach works correctly but will time out on large inputs. Let us improve it.

Approach 2: Expand Around Center

The key insight for this approach is that a palindrome mirrors around its center. Therefore, we can iterate through each possible center and expand outward as long as the characters on both sides match. Since there are 2n - 1 possible centers (each character for odd-length palindromes, and each gap between characters for even-length palindromes), and each expansion takes at most O(n) time, the overall complexity is O(n²).

How It Works

For each index i in the string, we perform two expansions:

We track the start and end indices of the longest palindrome found so far, updating them whenever we discover a longer one.

Implementation

package main

import "fmt"

func expandAroundCenter(s string, left, right int) (int, int) {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    // When the loop exits, left and right are one step beyond the palindrome.
    return left + 1, right - 1
}

func longestPalindromeExpand(s string) string {
    if len(s) < 2 {
        return s
    }

    start, end := 0, 0

    for i := 0; i < len(s); i++ {
        // Odd-length palindrome centered at i
        left1, right1 := expandAroundCenter(s, i, i)
        // Even-length palindrome centered between i and i+1
        left2, right2 := expandAroundCenter(s, i, i+1)

        if right1-left1 > end-start {
            start, end = left1, right1
        }
        if right2-left2 > end-start {
            start, end = left2, right2
        }
    }

    return s[start : end+1]
}

func main() {
    testCases := []string{"babad", "cbbd", "a", "ac", "racecar", "abacdfgdcaba"}
    for _, tc := range testCases {
        fmt.Printf("Input: %s -> Longest Palindrome: %s\n", tc, longestPalindromeExpand(tc))
    }
}

This approach is the sweet spot for most interviews and real-world scenarios. It runs in O(n²) time and uses only O(1) extra space, making it both efficient and easy to explain.

Approach 3: Dynamic Programming

Dynamic programming offers another O(n²) solution, but it uses O(n²) space to store a table of boolean values indicating whether a substring s[i:j] is a palindrome. While this is less space-efficient than the expand-around-center method, it is worth understanding because the DP pattern appears in many string problems.

How It Works

We define a 2D table dp[i][j] that is true if the substring from index i to index j is a palindrome. The recurrence relation is:

dp[i][j] = (s[i] == s[j]) AND (j - i < 2 OR dp[i+1][j-1])

This means a substring is a palindrome if its outer characters match and the inner substring is also a palindrome (or the substring has length 1 or 2). We fill the table by increasing substring length, which ensures that when we need dp[i+1][j-1], it has already been computed.

Implementation

package main

import "fmt"

func longestPalindromeDP(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }

    // dp[i][j] is true if s[i:j+1] is a palindrome
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
    }

    start, maxLen := 0, 1

    // Every single character is a palindrome
    for i := 0; i < n; i++ {
        dp[i][i] = true
    }

    // Check substrings of length 2 and greater
    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                if length == 2 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
                if dp[i][j] && length > maxLen {
                    start = i
                    maxLen = length
                }
            }
        }
    }

    return s[start : start+maxLen]
}

func main() {
    testCases := []string{"babad", "cbbd", "a", "ac", "racecar"}
    for _, tc := range testCases {
        fmt.Printf("Input: %s -> Longest Palindrome: %s\n", tc, longestPalindromeDP(tc))
    }
}

The DP approach is a great teaching tool, but in practice, the expand-around-center method is usually preferred because it achieves the same time complexity with constant space.

Approach 4: Manacher's Algorithm

For those who want the absolute best performance, Manacher's algorithm solves the problem in O(n) time. It achieves this by exploiting the symmetry of palindromes to avoid redundant comparisons. The algorithm is more complex to implement but is the gold standard for this problem.

How It Works

Manacher's algorithm works in three main steps:

Implementation

package main

import "fmt"

func longestPalindromeManacher(s string) string {
    if len(s) < 2 {
        return s
    }

    // Transform s into T with separators
    // Example: "aba" -> "^#a#b#a#$"
    // The '^' and '$' sentinels prevent bounds checking
    var T []byte
    T = append(T, '^')
    for i := 0; i < len(s); i++ {
        T = append(T, '#', s[i])
    }
    T = append(T, '#', '$')

    n := len(T)
    P := make([]int, n)
    C, R := 0, 0

    for i := 1; i < n-1; i++ {
        mirror := 2*C - i

        if i < R {
            if P[mirror] < R-i {
                P[i] = P[mirror]
            } else {
                P[i] = R - i
            }
        }

        // Expand around center i
        for T[i+1+P[i]] == T[i-1-P[i]] {
            P[i]++
        }

        // Update center and right boundary
        if i+P[i] > R {
            C = i
            R = i + P[i]
        }
    }

    // Find the maximum element in P
    maxLen, centerIndex := 0, 0
    for i := 1; i < n-1; i++ {
        if P[i] > maxLen {
            maxLen = P[i]
            centerIndex = i
        }
    }

    // Map back to original string
    start := (centerIndex - maxLen) / 2
    return s[start : start+maxLen]
}

func main() {
    testCases := []string{"babad", "cbbd", "a", "ac", "racecar", "abacdfgdcaba"}
    for _, tc := range testCases {
        fmt.Printf("Input: %s -> Longest Palindrome: %s\n", tc, longestPalindromeManacher(tc))
    }
}

Manacher's algorithm is the most efficient solution, but its complexity makes it harder to implement correctly under interview pressure. Practice it thoroughly before attempting it in a live setting.

Comparing the Approaches

Here is a summary of the four approaches we have covered:

For most practical purposes and interviews, the expand-around-center approach is the recommended choice. It is efficient, easy to explain, and uses minimal memory.

Best Practices

When implementing a solution to this problem, keep the following best practices in mind:

Testing Your Solution

Robust testing is essential for algorithmic problems. Here is a comprehensive test suite using Go's built-in testing framework that covers edge cases and typical scenarios:

package main

import "testing"

func TestLongestPalindromeExpand(t *testing.T) {
    tests := []struct {
        input    string
        expected int // expected length, since multiple valid answers may exist
    }{
        {"babad", 3},
        {"cbbd", 2},
        {"a", 1},
        {"ac", 1},
        {"racecar", 7},
        {"", 0},
        {"abacdfgdcaba", 3},
        {"aaaaaaaaaa", 10},
        {"abcdef", 1},
        {"bananas", 5},
    }

    for _, tt := range tests {
        result := longestPalindromeExpand(tt.input)
        if len(result) != tt.expected {
            t.Errorf("longestPalindromeExpand(%q) = %q (len %d), expected length %d",
                tt.input, result, len(result), tt.expected)
        }
        // Verify the result is actually a palindrome
        if len(result) > 0 && !isPalindrome(result, 0, len(result)-1) {
            t.Errorf("longestPalindromeExpand(%q) returned %q which is not a palindrome",
                tt.input, result)
        }
    }
}

func BenchmarkLongestPalindromeExpand(b *testing.B) {
    // Create a long string for benchmarking
    longString := ""
    for i := 0; i < 1000; i++ {
        longString += "a"
    }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        longestPalindromeExpand(longString)
    }
}

func BenchmarkLongestPalindromeManacher(b *testing.B) {
    longString := ""
    for i := 0; i < 1000; i++ {
        longString += "a"
    }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        longestPalindromeManacher(longString)
    }
}

Run the tests with go test -v and the benchmarks with go test -bench=.. You will likely see that Manacher's algorithm outperforms the expand-around-center method on very long strings, while for shorter inputs the difference is negligible.

Common Pitfalls

As you work through this problem, watch out for these common mistakes:

Conclusion

The Longest Palindromic Substring problem is a rich exercise that rewards careful thinking about string structure and algorithmic optimization. We explored four approaches in Go, ranging from the intuitive but slow brute force method to the optimal but intricate Manacher's algorithm. For most real-world applications and coding interviews, the expand-around-center technique offers the best combination of clarity, efficiency, and minimal memory usage. By understanding all four approaches, practicing the implementations, and writing thorough tests, you will be well-equipped to tackle this problem and many related string challenges with confidence. Remember that the journey from O(n³) to O(n) is itself a lesson in how recognizing structural properties of a problem can unlock dramatic performance improvements, a skill that will serve you throughout your career as a developer.

— Ad —

Google AdSense will appear here after approval

← Back to all articles