Open In App

Palindrome Substrings Count

Last Updated : 29 Aug, 2025
Suggest changes
Share
Like Article
Like
Report

Given a string s, find the total number of palindromic substrings of length greater than or equal to 2 present in the string.
A substring is palindromic if it reads the same forwards and backwards.

Examples:

Input: s = "abaab"
Output: 3
Explanation: Palindromic substrings with length greater than 1, are "aba", "aa", and "baab".

Input: s = "aaa"
Output: 3
Explanation: Palindromic substrings with length greater than 1, are "aa" , "aa" , "aaa" .

Input: s = "abbaeae"
Output: 4
Explanation: Palindromic substrings with length greater than 1, are "bb" , "abba" , "aea", "eae".

Table of Content

[Naive Approach] By Generating All Possible Substrings - O(n^3) Time and O(1) Space

The idea is to generate all possible substrings using two nested loops and for every substring check if it is palindrome or not.

C++ 
// C++ program to count all palindromic substring of // given string by generating all possible substrings #include <iostream> #include <string> using namespace std; // Function to check if a substring  // s[i..j] is a palindrome bool isPalindrome(string& s, int i, int j) {  while (i < j) {  if (s[i] != s[j]) return false;  i++;  j--;  }  return true; } int countPS(string& s) {  int n = s.length();     // Consider all possible substrings of lengths  // more than 1  int res = 0;  for (int i = 0; i < n; i++) {  for (int j = i+1; j < n; j++) {    // If substring from i to j is palindrome  // increment the result  if (isPalindrome(s, i, j))   res++;   }  }  return res; } int main() {  string s = "abaab";  cout << countPS(s);  return 0; }
Java 
// Java program to count all palindromic substring of // given string by generating all possible substrings class GfG {    // Function to check if a substring   // s[i..j] is a palindrome  static boolean isPalindrome(String s, int i, int j) {  while (i < j) {  if (s.charAt(i) != s.charAt(j)) return false;  i++;  j--;  }  return true;  }  static int countPS(String s) {  int n = s.length();  // Consider all possible substrings of lengths  // more than 1  int res = 0;  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {    // If substring from i to j is palindrome  // increment the result  if (isPalindrome(s, i, j))   res++;   }  }  return res;  }  public static void main(String[] args) {  String s = "abaab";  System.out.println(countPS(s));  } }
Python 
# Python program to count all palindromic substring of # given string by generating all possible substrings # Function to check if a substring  # s[i..j] is a palindrome def isPalindrome(s, i, j): while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return True def countPS(s): n = len(s) # Consider all possible substrings of lengths # more than 1 res = 0 for i in range(n): for j in range(i + 1, n): # If substring from i to j is palindrome # increment the result if isPalindrome(s, i, j): res += 1 return res if __name__ == "__main__": s = "abaab" print(countPS(s))
C# 
// C# program to count all palindromic substring of // given string by generating all possible substrings using System; class GfG {  // Function to check if a substring   // s[i..j] is a palindrome  static bool isPalindrome(string s, int i, int j) {  while (i < j) {  if (s[i] != s[j]) return false;  i++;  j--;  }  return true;  }  static int countPS(string s) {  int n = s.Length;  // Consider all possible substrings of lengths  // more than 1  int res = 0;  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {    // If substring from i to j is palindrome  // increment the result  if (isPalindrome(s, i, j))   res++;   }  }  return res;  }  static void Main() {  string s = "abaab";  Console.WriteLine(countPS(s));  } }
JavaScript 
// JavaScript program to count all palindromic substring  // of given string by generating all possible substrings function isPalindrome(s, i, j) {  while (i < j) {  if (s[i] !== s[j]) return false;  i++;  j--;  }  return true; } function countPS(s) {  let n = s.length;  // Consider all possible substrings of lengths  // more than 1  let res = 0;  for (let i = 0; i < n; i++) {  for (let j = i + 1; j < n; j++) {    // If substring from i to j is palindrome  // increment the result  if (isPalindrome(s, i, j))   res++;   }  }  return res; } // Driver Code let s = "abaab"; console.log(countPS(s));

Output
3

[Better Approach 1] Using Memoization - O(n^2) Time and O(n^2) Space

If we notice carefully, we can observe that this recursive solution holds the following two properties of Dynamic Programming:

1.Optimal Substructure: The solution for the problem isPalindrome(i, j) depends on the optimal solution of the subproblem isPalindrome(i + 1, j - 1). By solving the smaller substructures, we can efficiently find if the entire substring is a palindrome or not.

2.Overlapping Subproblems: We can see that we are computing the same subproblems multiple times, isPalindrome(i + 2, j - 2) will be computed in isPalindrome(i, j) as well as isPalindrome(i + 1, j - 1). This redundancy leads to overlapping subproblems.

  • There are two parameters(i and j) that change in the recursive solution and then can go from 0 to n. So we create a 2D array of size n x n for memoization.
  • We initialize this array as -1 to indicate nothing is computed initially. We first check if the value is -1, then only we make recursive calls.
  • If the substring from i to j is a palindrome, we store memo[i][j] = 1, otherwise 0.
C++ 
// C++ program to count all palindromic substring of // given string using memoization #include <iostream> #include <vector> #include <string> using namespace std; int isPalindrome(int i, int j, string& s,   vector<vector<int>>& memo) {    // One length string is always palindrome   if (i == j)  return 1;    // Two length string is plaindrome if  // both characters are same  if (j == i + 1 && s[i] == s[j])  return 1;    // if current substring is already checked  if (memo[i][j] != -1)  return memo[i][j];  // Check if the characters at i and j are equal   // and the substring inside is palindrome  memo[i][j] = (s[i] == s[j] &&   isPalindrome(i + 1, j - 1, s, memo));    return memo[i][j]; } int countPS(string& s) {  int n = s.length();    // Memoization table  vector<vector<int>> memo(n, vector<int>(n, -1));  int res = 0;  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {    // Check if the substring is palindrome  if (isPalindrome(i, j, s, memo)) {   res++;  }  }  }  return res; } int main() {  string s = "abaab";  cout << countPS(s);  return 0; }
Java 
// Java program to count all palindromic substring of given // string using memoization import java.util.Arrays; class GfG {  static int isPalindrome(int i, int j, String s,   int[][] memo) {  // One length string is always palindrome   if (i == j)  return 1;    // Two length string is palindrome if  // both characters are same  if (j == i + 1 && s.charAt(i) == s.charAt(j))  return 1;    // if current substring is already checked  if (memo[i][j] != -1)  return memo[i][j];  // Check if the characters at i and j are equal   // and the substring inside is palindrome  if(s.charAt(i) == s.charAt(j) &&   isPalindrome(i + 1, j - 1, s, memo) == 1)  memo[i][j] = 1;  else  memo[i][j] = 0;  return memo[i][j];  }  static int countPS(String s) {  int n = s.length();  // Memoization table  int[][] memo = new int[n][n];  for (int[] row : memo) {  Arrays.fill(row, -1);  }  int res = 0;  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {  // Check if the substring is palindrome  if (isPalindrome(i, j, s, memo) == 1) {  res++;  }  }  }  return res;  }  public static void main(String[] args) {  String s = "abaab";  System.out.println(countPS(s));  } }
Python 
# Python program to count all palindromic substrings of # a given string using memoization def isPalindrome(i, j, s, memo): # One length string is always palindrome  if i == j: return 1 # Two length string is palindrome if # both characters are same if j == i + 1 and s[i] == s[j]: return 1 # if current substring is already checked if memo[i][j] != -1: return memo[i][j] # Check if the characters at i and j are equal  # and the substring inside is palindrome if s[i] == s[j] and isPalindrome(i + 1, j - 1, s, memo) == 1: memo[i][j] = 1 else: memo[i][j] = 0 return memo[i][j] def countPS(s): n = len(s) # Memoization table memo = [[-1 for i in range(n)] for i in range(n)] res = 0 for i in range(n): for j in range(i + 1, n): # Check if the substring is palindrome if isPalindrome(i, j, s, memo) == 1: res += 1 return res if __name__ == "__main__": s = "abaab" print(countPS(s))
C# 
// C# program to count all palindromic substrings of // a given string using memoization using System; class GfG {  static int IsPalindrome(int i, int j, string s,   int[,] memo) {  // One length string is always palindrome   if (i == j)  return 1;  // Two length string is palindrome if  // both characters are same  if (j == i + 1 && s[i] == s[j])  return 1;  // if current substring is already checked  if (memo[i, j] != -1)  return memo[i, j];  // Check if the characters at i and j are equal   // and the substring inside is palindrome  if (s[i] == s[j] &&   IsPalindrome(i + 1, j - 1, s, memo) == 1) {  memo[i, j] = 1;  }   else {  memo[i, j] = 0;  }  return memo[i, j];  }  static int CountPS(string s) {  int n = s.Length;  // Memoization table  int[,] memo = new int[n, n];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  memo[i, j] = -1;  }  }  int res = 0;  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {  // Check if the substring is palindrome  if (IsPalindrome(i, j, s, memo) == 1) {  res++;  }  }  }  return res;  }  static void Main() {  string s = "abaab";  Console.WriteLine(CountPS(s));  } }
JavaScript 
// JavaScript program to count all palindromic substrings of // a given string using memoization function isPalindrome(i, j, s, memo) {    // One length string is always palindrome   if (i === j)   return 1;    // Two length string is palindrome if  // both characters are same  if (j === i + 1 && s[i] === s[j])   return 1;    // if current substring is already checked  if (memo[i][j] !== -1)   return memo[i][j];    // Check if the characters at i and j are equal   // and the substring inside is palindrome  if (s[i] === s[j] &&   isPalindrome(i + 1, j - 1, s, memo) === 1)   memo[i][j] = 1;  else   memo[i][j] = 0;    return memo[i][j]; } function countPS(s) {  const n = s.length;    // Memoization table  const memo = Array.from({ length: n }, () => Array(n).fill(-1));  let res = 0;  for (let i = 0; i < n; i++) {  for (let j = i + 1; j < n; j++) {    // Check if the substring is palindrome  if (isPalindrome(i, j, s, memo) === 1) {   res++;  }  }  }  return res; } // Driver Code const s = "abaab"; console.log(countPS(s));

Output
3

[Better Approach 2] Using Bottom-Up DP (Tabulation) - O(n^2) Time and O(n^2) Space

We create a dp array of size n x n. However, we cannot simply fill the dp table from i = 0 to n-1 and j from i to n-1. To compute the value for (i, j), we need the value from (i+1, j-1). Similar to Matrix Chain Multiplication, we need to fill the table diagonally using a gap variable.

1. Base Cases:
=> A single character string is always palindrome, i.e. dp[i][i] = true.
=> Strings having two characters are palindrome, if both the characters are same. i.e. dp[i][i+1] = true if s[i] == s[i+1].

2. Any substring s[i...j] will be palindrome if:
=> If first and last characters of string are same
=> Remaining substring (excluding first and last character) is palindrome. I.e. dp[i+1][j-1] = true.

Illustration:


C++ 
// C++ program to count all palindromic substring of // given string using bottom up DP #include <iostream> #include <vector> #include <string> using namespace std; int countPS(string& s) {  int n = s.length();  int res = 0;  vector<vector<bool>> dp(n, vector<bool>(n, false));    // One length string is always palindrome   for (int i = 0; i < n; i++) {  dp[i][i] = true;  }  // Two length string is plaindrome if  // both characters are same  for (int i = 0; i < n - 1; i++) {  if (s[i] == s[i + 1]) {  dp[i][i + 1] = true;  res++;  }  }  // Handle palindromes of length   // greater than 2 (gap >= 2)  for (int gap = 2; gap < n; gap++) {  for (int i = 0; i < n - gap; i++) {  int j = i + gap;  // Check if the current string is a palindrome  if (s[i] == s[j] && dp[i + 1][j - 1]) {  dp[i][j] = true;  res++;  }  }  }    return res; } int main() {  string s = "abaab";  cout << countPS(s) << endl;  return 0; }
Java 
// Java program to count all palindromic substrings of // given string using bottom-up DP import java.util.*; class GfG {  static int countPS(String s) {  int n = s.length();  int res = 0;  boolean[][] dp = new boolean[n][n];  // One length string is always palindrome   for (int i = 0; i < n; i++) {  dp[i][i] = true;  }  // Two length string is palindrome if  // both characters are same  for (int i = 0; i < n - 1; i++) {  if (s.charAt(i) == s.charAt(i + 1)) {  dp[i][i + 1] = true;  res++;  }  }  // Handle palindromes of length greater than 2  for (int gap = 2; gap < n; gap++) {   for (int i = 0; i < n - gap; i++) {  int j = i + gap;  // Check if the current string is a palindrome  if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {  dp[i][j] = true;  res++;  }  }  }  return res;  }  public static void main(String[] args) {  String s = "abaab";  System.out.println(countPS(s));  } }
Python 
# Python program to count all palindromic substrings of # given string using bottom-up DP def countPS(s): n = len(s) res = 0 dp = [[False] * n for i in range(n)] # One length string is always palindrome  for i in range(n): dp[i][i] = True # Two length string is palindrome if # both characters are same for i in range(n - 1): if s[i] == s[i + 1]: dp[i][i + 1] = True res += 1 # Handle palindromes of length  # greater than 2 (gap >= 2) for gap in range(2, n): for i in range(n - gap): j = i + gap # Check if the current string is a palindrome if s[i] == s[j] and dp[i + 1][j - 1]: dp[i][j] = True res += 1 return res if __name__ == "__main__": s = "abaab" print(countPS(s))
C# 
// C# program to count all palindromic substrings of // given string using bottom-up DP using System; class GfG {  static int countPS(string s) {  int n = s.Length;  int res = 0;  bool[,] dp = new bool[n, n];  // One length string is always palindrome   for (int i = 0; i < n; i++) {  dp[i, i] = true;  }  // Two length string is palindrome if  // both characters are same  for (int i = 0; i < n - 1; i++) {  if (s[i] == s[i + 1]) {  dp[i, i + 1] = true;  res++;  }  }  // Handle palindromes of length   // greater than 2 (gap >= 2)  for (int gap = 2; gap < n; gap++) {  for (int i = 0; i < n - gap; i++) {  int j = i + gap;  // Check if the current string is a palindrome  if (s[i] == s[j] && dp[i + 1, j - 1]) {  dp[i, j] = true;  res++;  }  }  }  return res;  }  static void Main() {  string s = "abaab";  Console.WriteLine(countPS(s));  } }
JavaScript 
// JavaScript program to count all palindromic substrings of // given string using bottom-up DP function countPS(s) {  const n = s.length;  let res = 0;  const dp = Array.from({ length: n }, () => Array(n).fill(false));  // One length string is always palindrome   for (let i = 0; i < n; i++) {  dp[i][i] = true;  }  // Two length string is palindrome if  // both characters are same  for (let i = 0; i < n - 1; i++) {  if (s[i] === s[i + 1]) {  dp[i][i + 1] = true;  res++;  }  }  // Handle palindromes of length   // greater than 2 (gap >= 2)  for (let gap = 2; gap < n; gap++) {  for (let i = 0; i < n - gap; i++) {  const j = i + gap;  // Check if the current string is a palindrome  if (s[i] === s[j] && dp[i + 1][j - 1]) {  dp[i][j] = true;  res++;  }  }  }  return res; } // Driver Code const s = "abaab"; console.log(countPS(s));

Output
3

Expected Approach - Continued article

This problem can be solved more efficiently using Manacher’s algorithm or the center expansion technique.
See: Count All Palindrome Sub-Strings Set 2

Related article:


K

kartik

Explore

Article Tags :
Lightbox