# 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是二维数组。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/palindromic/palindromic-substrings.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.