Longest Palindromic Substring

Medium

The problem

A palindrome reads the same forwards and backwards. Return the longest substring of s (a run of neighbouring characters) that is a palindrome. If several are equally long, return the one that starts first.

Example 1
Input: s = "cbbd"
Output: "bb"
Example 2
Input: s = "forgeeksskeegfor"
Output: "geeksskeeg"
It reads the same in both directions and nothing longer does.
Example 3
Input: s = "abacdfgdcaba"
Output: "aba"
"aba" appears twice; the first one is returned.

Limits

1 ≤ len(s) ≤ 1,000
s has only letters and digits

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Every palindrome has a centre. How many possible centres are there?

The idea

For each of the 2n−1 centres expand outward while the characters match; keep the longest.

Target: O(n²) time, O(1) space

Go function shape

func longestPalindrome(s string) string

Reference solution

Tested with go test. Try it yourself first, then compare.

// LongestPalindrome: every palindrome has a centre, and there are 2n-1 centres
// (n letters and n-1 gaps between letters). Expand outward from each while the ends match.
func LongestPalindrome(s string) string {
	start, length := 0, 0
	expand := func(l, r int) {
		for l >= 0 && r < len(s) && s[l] == s[r] {
			l--
			r++
		}
		if r-l-1 > length {
			start, length = l+1, r-l-1
		}
	}
	for i := range s {
		expand(i, i)   // odd length, centred on a letter
		expand(i, i+1) // even length, centred between two letters
	}
	return s[start : start+length]
}

// CountSubstrings: the same expansion, counting every success instead of keeping the longest.
func CountSubstrings(s string) int {
	count := 0
	expand := func(l, r int) {
		for l >= 0 && r < len(s) && s[l] == s[r] {
			count++
			l--
			r++
		}
	}
	for i := range s {
		expand(i, i)
		expand(i, i+1)
	}
	return count
}

Read the lesson: Dynamic Programming