Palindromic Substrings

class Solution {
    public int countSubstrings(String s) {
        int count=0;
        for(int i=0;i<s.length();i++){
            count+=expand(s,i,i);//palindromes of the form WCW'
            count+=expand(s,i,i+1);//palindromes of the form WW'
        }
        return count;
    }
    private int expand(String s,int start,int end){

        int len=0;
        while(start>=0 && end<s.length() && s.charAt(start)==s.charAt(end)){
            len++;
            start--;
            end++;
        }
        return len;
    }
}

Enter fullscreen mode Exit fullscreen mode

There are basically two types of palindromes, odd length and even length.
Odd length palindromes are of the form WCW’
for example, DAD, MOM, RACECAR. In all of these examples there’s one character that separates the equivalent characters around it. To satisfy this condition we compare the character to itself and then go on expanding around it as the code shows. This is also the case of single characters where the character itself is a palindrome considering the Ws on both sides to be null.
W’ being the reverse of W.

On the other hand, for even palindromic strings like bb, aa, you directly compare it with the character right next to it. If it is a palindrome the characters match and you move forwards in W’ and backwards in W thereby comparing the characters at the same position but in reverse.

原文链接：Palindromic Substrings