Palindromic Substrings

Medium

The problem

Count how many substrings of s (runs of neighbouring characters) are palindromes. Substrings at different positions count separately, even if they have the same letters.

Example 1
Input: s = "abc"
Output: 3
Only the single letters "a", "b" and "c".
Example 2
Input: s = "aaa"
Output: 6
"a" three times, "aa" twice and "aaa" once.

Limits

1 ≤ len(s) ≤ 1,000
s has only lowercase English letters

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

Same centre-expansion idea, but count every successful expansion.

The idea

Expand around each centre (odd and even) and add 1 for every palindrome found.

Target: O(n²) time

Go function shape

func countSubstrings(s string) int

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