647. Palindromic Substrings

Problem

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

1. The input string length won't exceed 1000.

Problem Summary

Given a string, your task is to count how many palindromic substrings there are in this string. Substrings with different start positions or end positions are considered different substrings, even if they consist of the same characters.

Solution Approach

• Brute-force solution: scan the string from left to right, use each character as the center, and use the center expansion method to traverse and count palindromic substrings in order.

Code

package leetcode

func countSubstrings(s string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		res += countPalindrome(s, i, i)
		res += countPalindrome(s, i, i+1)
	}
	return res
}

func countPalindrome(s string, left, right int) int {
	res := 0
	for left >= 0 && right < len(s) {
		if s[left] != s[right] {
			break
		}
		left--
		right++
		res++
	}
	return res
}