Longest Palindromic Substring in Go

This Go program finds the longest palindromic substring in a given string. A palindrome is a string that reads the same forward and backward.

Program Code

package main

import (
    "fmt"
)

// Function to expand around the center and find the longest palindrome
func expandAroundCenter(s string, left int, right int) string {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return s[left+1 : right]
}

// Function to find the longest palindromic substring
func longestPalindrome(s string) string {
    if len(s) == 0 {
        return ""
    }
    
    longest := ""
    for i := 0; i < len(s); i++ { // Check for odd-length palindromes oddPalindrome := expandAroundCenter(s, i, i) if len(oddPalindrome) > len(longest) {
            longest = oddPalindrome
        }
        
        // Check for even-length palindromes
        evenPalindrome := expandAroundCenter(s, i, i+1)
        if len(evenPalindrome) > len(longest) {
            longest = evenPalindrome
        }
    }
    return longest
}

func main() {
    str := "babad"
    fmt.Printf("Longest palindromic substring of \"%s\" is \"%s\"\n", str, longestPalindrome(str))
}
    

Program Explanation

The program is structured as follows:

1. Import Packages: The fmt package is imported for formatted I/O operations.
2. Function expandAroundCenter: This function takes a string and two indices (left and right) as parameters. It expands around these indices as long as the characters at these positions are equal and within bounds. It returns the longest palindromic substring found during this expansion.
3. Function longestPalindrome: This function iterates through each character in the string, using expandAroundCenter to find both odd-length and even-length palindromes centered at each character. It updates the longest palindromic substring found.
4. Main Function: The main function initializes a test string and prints the longest palindromic substring found using the longestPalindrome function.

How to Run

1. Save the code to a file named main.go.
2. Open a terminal or command prompt and navigate to the directory containing main.go.
3. Run the command go run main.go to execute the program.

Example Output

For the input string "babad", the output will be:

Longest palindromic substring of "babad" is "bab"
    

Explanation

1. expandAroundCenter Function: This function checks for the longest palindrome around a given center. It expands outwards from the center until the characters differ or boundaries are reached, and then returns the substring that is a palindrome.
2. longestPalindrome Function: This function iterates through each character of the string and uses expandAroundCenter to find palindromic substrings. It considers both odd and even-length palindromes and keeps track of the longest one found.
3. main Function: It tests the longestPalindrome function with a sample string and prints the result.