Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = “abc” Output: 3 Explanation: Three palindromic strings: “a”, “b”, “c”. Example 2:

Input: s = “aaa” Output: 6 Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

<解題>

1. 由中間出發往兩側搜尋是否為回文->奇數長度(中間為相同) ex: cbc ->偶數長度(中間兩個為相同) ex: cbbc
2. 往兩側拓展至一方over boundary，當中分別計算回文的數量

class Solution {
    public int countSubstrings(String s) {
        if(s.length()==0) return 0;
        int n = s.length();
        int res = 0;
        char[] c = s.toCharArray();

        for(int i =0; i<n; i++){
            res +=isPalindromic(i,i,c);
            res +=isPalindromic(i,i+1,c);
        }
        return res;
    }
    public int isPalindromic(int s, int e, char[]c){
        int count =0;
        while(s>=0 && e < c.length && c[s--]==c[e++]){
            count++;
        }
        return count;
    }
}

Time: O() Space: O()