# LC 647. Palindromic Substrings

### [Problem link](https://leetcode.com/problems/palindromic-substrings/)

###### tags: `leedcode` `python` `medium` `c++` `DP` `Two Pointer`

Given a string <code>s</code>, 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".

**Constraints:**

- <code>1 <= s.length <= 1000</code>
- <code>s</code> consists of lowercase English letters.

## Solution 1 - DP
#### Python

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        res = 0
        dp = [[False] * n for _ in range(n)]
        # dp[i][j]: whether s[i:j+1] is a palindrome substring.

        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 1 or dp[i + 1][j - 1]:
                        dp[i][j] = True
                        res += 1

        return res

#### C++

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int res = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i >= 2) {
                        dp[i][j] = dp[i + 1][j - 1];
                    } else {
                        dp[i][j] = true;
                    }
                    if (dp[i][j]) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

## Solution 2 - Two Pointer
#### Python

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        res = 0

        def get_pali_substr_num(left, right):
            num = 0
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
                num += 1
            return num

        for i in range(n):
            res += get_pali_substr_num(i, i)
            res += get_pali_substr_num(i, i + 1)

        return res

#### C++

class Solution {
public:
    int cntSubStr(string& s, int left, int right) {
        int cnt = 0;
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
            cnt++;
        }
        return cnt;
    }

    int countSubstrings(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            res += cntSubStr(s, i, i);
            res += cntSubStr(s, i, i + 1);
        }
        return res;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O($n^2$) |
>| Solution 2 | O($n^2$) | O(1) |

## Note
[代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.md)

sol1:
dp[i][j] = s[i: j + 1]是否是回文字串

if s[i] == s[j]:
    有三種情況:
        1. i == j, ex: a
        2. j - i == 1, ex: aa
        3. j - i > 1, ex: abcba
    第三種情況需要找到dp[i + 1][j - 1], 來確認是否是回文

sol2:
以s[i]或s[i:i+1]為中心向左右擴散確認是否是回文.

與[LC 5. Longest Palindromic Substring](https://hackmd.io/@Alone0506/r11Du5y52)類似