# Leetcode 647 Palindromic Substrings (Medium)

Kumar Pallav
·Aug 14, 2021·

Subscribe to my newsletter and never miss my upcoming articles

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