Palindromic Substrings

First Solution

From a DP perspective, we need all substrings. So we use a 2D array to store results. dp[i][j] means the string from index i to j is a palindrome.

If i == j, we increment the counter and mark dp[i][j] as 1. If the length from i to j is 2, then s[i] == s[j] makes it a palindrome. If the length is greater than 2, we expand outward. If the new left and right characters are equal and the original string was a palindrome, then the new string is also a palindrome.

int countSubstrings(string s) {
    int len=s.size();
    int res=0;
    vector<vector<bool> > dp(s.size(), vector<bool>(s.size(), false));
    // Length 1
    for(int i=0;i<len;++i) {
        ++res;
        dp[i][i]=true;
    }
    // Length 2
    for(int i=1;i<len;++i) {
        if(s[i]==s[i-1]) {
            ++res;
            dp[i-1][i]=true;
        }
    }
    // Length 3 ~ N
    for(int i=len-3;i>=0;--i) {
        for(int j=i+2;j<len;++j) {
            if (s[i]==s[j] && dp[i+1][j-1]) {
                ++res;
                dp[i][j]=true;
            }
        }
    }
    return res;
}

Second Solution: Direct Expansion

The symmetric center of a palindrome can be any character in the string or between two adjacent characters.

int countSubstrings(string s) {
    int res=0;
    for(int i=0;i<s.size();++i) {
        countPalin(s, i, i, res);    // Odd length palindromes
        countPalin(s, i, i+1, res);  // Even length palindromes
    }
    return res;
}

void countPalin(string &s, int i, int j, int &res) {
    while(i>=0 && j<s.size() && s[i--]==s[j++]) ++res;
}

#DP

Palindrome Partitioning with Backtracking Pancake Sorting: Flip Your Way to Order