> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/palindromic/palindromic-substrings.md).

# 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.

## Thoughts

统计S中所有满足回文的子串个数。回文 + 统计个数，直观想法是用DP判断所有子串是否回文，global记录下结果。

利用回文的性质，对每个元素从两边拓展看能否组成回文。拓展的方式有长度为奇数和偶数两种。时间复杂度虽然没变，但实际基本不会每个子串都检查一遍，lc上时间beats 100%。空间复杂度也降到了O(1)。

## Code

```cpp
// @lc code=start
class Solution {
public:
    int countSubstrings(string s) {
        const int N = s.length();
        int res = 0;
        const auto ext = [&](string &s, int l, int r) {
            while (l >= 0 && r < N && s[l--] == s[r++]) {
                ++res;
            }
        };
        for (int i = 0; i < N; ++i) {
            ext(s, i, i);
            ext(s, i, i + 1);
        }
        return res; 
    }
};
// @lc code=end
```

```cpp
/*
 * @lc app=leetcode id=647 lang=cpp
 *
 * [647] Palindromic Substrings
 */

// @lc code=start
class Solution {
public:
    int countSubstrings(string s) {
        const int N = s.length();
        vector<vector<bool>> dp(N, vector<bool>(N, false));
        int res = N;
        for (int i = 0; i < N; ++i) dp[i][i] = true;
        for (int i = N - 1; i >= 0; --i) {
            for (int j = i + 1; j < N; ++j) {
                if (s[i] == s[j] && (i == j - 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ++res;
                }
            }
        }
        return res; 
    }
};
// @lc code=end
```

## Analysis

Errors:

1. corner cases

时间复杂度是两次O(n^2), 因为f是二维数组。