# 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

hnode.com/res/hashnode/image/upload/v162895..)

## 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;
}
}
```