# Leetcode 647 Palindromic Substrings (Medium)


# 647. Palindromic Substrings -Leetcode 
## Question
Given a string  `s`, 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:**

-   `1 <= s.length <= 1000`
-   `s`  consists of lowercase English letters.

## Intution

 - Any String which is of a single character is a palindrome i.e. a,b,c,d,e etc all are palindrome.

 -  For a string of 2 character it is a palindrome if both characters are same  i.e. 0th and 1st character are same. aa,bb,cc,dd etc are palindrome but ab,ba,cf are not palindrome
 
-  Any String of more than 3  characters are palindrome if the first and last character are same and the Substrings within first and last character is a palindrome.
## Implementation
Let us represent String in a matrix of n x n , where n is the length of the matrix. 
For example if we take the string as "abcba" we will create a matrix of nxn .
In this matrix rows represent starting position and column will represent the ending position of the substring.
Below pics tell walk us step by step to approach used in intution

![Number of pallindrome substring.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953348096/gJjOZLrQw.jpeg)


![Number of pallindrome substring (1).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953364365/Ol7ZsbpwT.jpeg)

![Number of pallindrome substring (2).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953374734/Mn0fqr1Aa.jpeg)

![Number of pallindrome substring (3).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953404038/7a1kF8vYk.jpeg)

![Number of pallindrome substring (4).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953418892/VmgujNLrV.jpeg)


![Number of pallindrome substring (5).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953511185/6OFMrF5Xu.jpeg)

![Number of pallindrome substring (6).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953441605/jReim9KYq.jpeg)
hnode.com/res/hashnode/image/upload/v1628953434477/mJeyDfunW.jpeg)

![Number of pallindrome substring (7).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1628953528536/etVpXSndU.jpeg)

## Code in Java
Let us look at actual code implementation of the solution

```
class Solution {
    public int countSubstrings(String s) {
        int m = s.length();
        int n = m;
        int count = 0;
        boolean[][] p = new boolean[m][n];
        for (int k = 0; k < n; k++) {
            int i = 0;
            int j = k;
            while (i < m && j < n) {
                if (i == j) {
                    p[i][j] = true;
                } else if (j - i == 1 && s.charAt(i) == s.charAt(j)) {
                    p[i][j] = true;
                } else if (s.charAt(i) == s.charAt(j) && p[i + 1][j - 1])
                    p[i][j] = true;
                if (p[i][j])
                    count++;
                i++;
                j++;
            }
        }

        return count;
    }
}
```