# Solution For Palindromic Substrings

Problem Description:

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 substrings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

Approach:

The solution to this problem can be achieved using Dynamic Programming. For a string to be palindromic, it should have 1 or 2 characters repeating at the beginning and end of each subproblem. We can use a two-dimensional boolean array to keep track of the subproblems. So, if we have a palindromic substring substring(i, j), then substring(i+1, j-1) should also be a palindromic substring if the characters at position i and j are equal.

Algorithm:

1. Initialize a two-dimensional boolean array dp of size n x n, where n is the length of the string s.
2. Initialize a count variable to 0.
3. Traverse the string s from the end and for each index i:
a. Traverse the string s from i to the end and for each index j:
i. If i and j are equal, set the value of dp[i][j] to True
ii. If the value of dp[i][j] is True, increase the count by 1.
4. Return the count.

Code:

public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;

``````    for(int i=n-1; i>=0; i--){
for(int j=i; j<n; j++){
if(s.charAt(i) == s.charAt(j)){
if(j-i+1 <= 2)
dp[i][j] = true;
else
dp[i][j] = dp[i+1][j-1];
}
if(dp[i][j])
count++;
}
}
return count;
}
``````

Time Complexity: O(n^2)
Space Complexity: O(n^2)

## Step by Step Implementation For Palindromic Substrings

```public class Solution {
public int countSubstrings(String s) {
int n = s.length();
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (isPalindrome(s, i, j)) {
res++;
}
}
}
return res;
}

private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
}```
```class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
# Solution:
# We can solve this problem by keeping track of the number of
# palindromic substrings as we iterate through the string.
# We can do this by maintaining a 2D boolean array, where
# dp[i][j] is true if the substring s[i:j+1] is a palindrome.
# We can then compute the number of palindromic substrings by
# summing up the number of dp[i][j] that are true.

# The base cases are when i == j, which is always a palindrome,
# and when i == j - 1. If s[i] == s[j], then it's a palindrome
# if dp[i+1][j-1] is a palindrome. Otherwise, it's not a palindrome.

# We can then fill in the rest of the dp array in a bottom-up fashion.

# Time Complexity: O(n^2)
# Space Complexity: O(n^2)

# Initialize 2D boolean array
n = len(s)
dp = [[False] * n for _ in range(n)]

# Base cases
for i in range(n):
dp[i][i] = True
for i in range(n-1):
dp[i][i+1] = s[i] == s[i+1]

# Fill in rest of array in bottom-up fashion
for j in range(2, n):
for i in range(0, j-1):
dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

# Sum up number of dp[i][j] that are true
count = 0
for i in range(n):
for j in range(n):
if dp[i][j]:
count += 1

return count```
```var countSubstrings = function(s) {
let n = s.length, ans = 0;
for (let i = 0; i < 2 * n - 1; ++i) {
let l = i / 2, r = i / 2 + i % 2;
while (l >= 0 && r < n && s[l] == s[r]) {
--l;
++r;
++ans;
}
}
return ans;
};```
```class Solution {
public:
int countSubstrings(string s) {
int n = s.length();
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
if(isPalindrome(s.substr(i, j-i+1))) {
ans++;
}
}
}
return ans;
}

bool isPalindrome(string s) {
int n = s.length();
for(int i = 0; i < n/2; i++) {
if(s[i] != s[n-1-i]) {
return false;
}
}
return true;
}
};```
```public class Solution {
public int CountSubstrings(string s) {
int count = 0;

for (int i = 0; i < s.Length; i++) {
//odd length
count += ExpandFromMiddle(s, i, i);
//even length
count += ExpandFromMiddle(s, i, i + 1);
}

return count;
}

private int ExpandFromMiddle(string s, int left, int right) {
int count = 0;

while (left >= 0 && right < s.Length && s[left] == s[right]) {
count++;
left--;
right++;
}

return count;
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]