Palindromic Substrings

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

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

一个O(n^2)的解法

中心扩散法

Code

class Solution {
    int count = 0;
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        for (int i = 0; i < s.length(); i++) {
            helper(s, i, i);
            helper(s, i, i + 1);
        }

        return count;
    }

    private void helper(String s, 
                        int left, int right) {
        while (left >= 0 && right < s.length() && 
               s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
    }
}