# Palindromic Substrings Leetcode Solution

Difficulty Level Medium
Dynamic Programming StringViews 1478

## Problem Statement

The Palindromic Substrings LeetCode Solution – “Palindromic Substrings” asks you to find a total number of palindromic substrings in the input string.

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:

`Input:  s = "aaa"`
`Output: 6`

Explanation:

• All substrings are: [a,a,a,aa,aa,aaa].
• All the above substrings are palindrome, hence the answer is 6.
`Input:  s = "abc"`
`Output: 3`

Explanation:

• All substrings are: [a,b,c,ab,bc,abc].
• Palindromic substrings are: [a,b,c]. Hence the answer is 3.

## Approach

### Idea:

1. The main idea to solve this problem is to use dynamic programming.
2. Maintain a boolean 2D vector that stores whether the substring [i:j] is a palindrome or not.
3. We’ll iterate for smaller-length substrings then move on to higher-length substrings.
4. dynamic programming relation is given by: dp[i][j]=true if s[i]==s[j] and dp[i+1][j-1]==true.
5. After filling the boolean matrix, we’ll iterate for all the substrings and increment our answer by 1 if the substring is a palindrome.

## Code for Palindromic Substrings Leetcode Solution:

### C++ Solution:

```class Solution {
public:
int countSubstrings(string s) {
int n = s.length();
vector<vector<bool>> dp(n,vector<bool>(n));
for(int i=0;i<n;i++){
dp[i][i] = true;
}
for(int L=2;L<=n;L++){
for(int i=0;i+L<=n;i++){
int j = i + L - 1;
if(L==2){
dp[i][j] = s[i]==s[j];
}
else if(s[i]==s[j] and dp[i+1][j-1]){
dp[i][j] = true;
}
}
}
int ans = 0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
ans += dp[i][j];
}
}
return ans;
}
};```

### Java Solution:

```class Solution {
public int countSubstrings(String s) {
int n = s.length(),res = 0;
boolean[][] dp = new boolean[n][n];
for(int i=0;i<n;i++){
dp[i][i] = true;
}
for(int L=2;L<=n;L++){
for(int i=0;i+L<=n;i++){
int j = i + L - 1;
if(L==2){
dp[i][j] = s.charAt(i)==s.charAt(j);
}
else if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]){
dp[i][j] = true;
}
}
}
int ans = 0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
if(dp[i][j]){
ans++;
}
}
}
return ans;
}
}```

## Complexity Analysis for Palindromic Substrings Leetcode Solution

### Time Complexity

The time complexity of the above code is O(N^2) since we traverse for every substring which takes O(N^2) time.

### Space Complexity

The space complexity of the above code is O(N^2). A 2D vector of size N*N has been made to store answers for every substring.

Reference: https://en.wikipedia.org/wiki/Palindrome

Translate »