Find all distinct palindromic sub-strings of a given string

Last Updated : 06 Dec, 2023

Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it.

Examples:

Input: str = "abaaa"
Output:  Below are 5 palindrome sub-strings
a
aa
aaa
aba
b
Input: str = "geek"
Output:  Below are 4 palindrome sub-strings
e
ee
g
k

BRUTE APPROACH

Intuition:

We declare a boolean 2-D array and fill it diagonally.

We check for every gap.ie(0,1,2,…..)

suppose gap=0., that means there is only one element and we put true since a single character is palindrome

if gap = 1, we check whether extremes are same and if so we put true,else false;

else for any other value of gap, we check if extremes are same and dp[i+1][j-1] yields true and if so then we put true else false;

at every time when a true is encountered we add the string in the set data structure.

Atlast we return the ans

Implementation:

C++

#include <iostream>
#include <set>
using namespace std;
 
// Function to find all distinct palindrome 
// substrings in a given string
int GFG(string str, set<string> &result) {
    int n = str.length();
    bool dp[n][n];
    for (int gap = 0; gap < n; gap++) {
        for (int i = 0, j = gap; j < n; i++, j++) {
            if (gap == 0)
                dp[i][j] = true; 
          // Single characters are palindromes
            else if (gap == 1)
                dp[i][j] = (str[i] == str[j]); 
          // Two characters are palindromes if they are the same
            else
                dp[i][j] = (str[i] == str[j] && dp[i + 1][j - 1]); 
          // Check if the substring is a palindrome
            if (dp[i][j])
                result.insert(str.substr(i, j - i + 1));
        }
    }
    return result.size(); 
  // Return the count of distinct palindromic substrings
}
int main() {
    string str = "abaaa";
    set<string> result;
    // Call the function to find palindromic substrings
    GFG(str, result);
    cout << "Number of distinct palindromic substrings are: " << result.size() << endl;
    // Print the distinct palindromic substrings
    for (const string &s : result)
        cout << s << endl;
    return 0;
}

Java

// Java program to find all distinct palindrome
// sub-strings of a given string
 
import java.io.*;
import java.util.*;
 
class GFG {
    static int palindromeSubStrs(String str,
                                 Set<String> set)
    {
        // code here
        int n = str.length();
        boolean dp[][] = new boolean[n][n];
 
        for (int gap = 0; gap < n; gap++) {
            for (int i = 0, j = gap; j < n; i++, j++) {
                if (gap == 0)
                    dp[i][j] = true;
                else if (gap == 1)
                    dp[i][j]
                        = str.charAt(i) == str.charAt(j);
                else
                    dp[i][j]
                        = (str.charAt(i) == str.charAt(j)
                           && dp[i + 1][j - 1]);
 
                if (dp[i][j])
                    set.add(str.substring(i, j + 1));
            }
        }
        return set.size();
    }
    public static void main(String[] args)
    {
        String str = "abaaa";
        Set<String> set = new TreeSet<>();
        palindromeSubStrs(str, set);
        System.out.println(
            "No of distinct palindromic substrings are : "
            + palindromeSubStrs(str, set));
 
        for (String s : set)
            System.out.println(s);
    }
}
// This code is contributed by Raunak Singh

Python3

def palindromeSubStrs(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    distinct_palindromes = set()
 
    for gap in range(n):
        for i in range(n - gap):
            j = i + gap
            if gap == 0:
                dp[i][j] = True
            elif gap == 1:
                dp[i][j] = s[i] == s[j]
            else:
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
 
            if dp[i][j]:
                distinct_palindromes.add(s[i:j + 1])
 
    return distinct_palindromes
 
 
if __name__ == "__main__":
    s = "abaaa"
    palindromes = palindromeSubStrs(s)
    print("No of distinct palindromic substrings are:", len(palindromes))
    for palindrome in palindromes:
        print(palindrome)

C#

// C# program to find all distinct palindrome
// sub-strings of a given string
using System;
using System.Collections.Generic;
 
class GFG
{
    static int PalindromeSubStrs(string str, HashSet<string> set)
    {
      // code here
        int n = str.Length;
        bool[,] dp = new bool[n, n];
 
        for (int gap = 0; gap < n; gap++)
        {
            for (int i = 0, j = gap; j < n; i++, j++)
            {
                if (gap == 0)
                    dp[i, j] = true;
                else if (gap == 1)
                    dp[i, j] = str[i] == str[j];
                else
                    dp[i, j] = (str[i] == str[j] && dp[i + 1, j - 1]);
 
                if (dp[i, j])
                    set.Add(str.Substring(i, j - i + 1));
            }
        }
        return set.Count;
    }
 
    public static void Main(string[] args)
    {
        string str = "abaaa";
        HashSet<string> set = new HashSet<string>();
        PalindromeSubStrs(str, set);
        Console.WriteLine(
            "No of distinct palindromic substrings are: " +
            PalindromeSubStrs(str, set));
 
        foreach (string s in set)
            Console.WriteLine(s);
    }
}

Javascript

// Function to find all distinct palindrome substrings in a given string
function findDistinctPalindromicSubstrings(str) {
    const n = str.length;
    const dp = Array(n).fill(0).map(() => Array(n).fill(false));
    const result = new Set();
 
    for (let gap = 0; gap < n; gap++) {
        for (let i = 0, j = gap; j < n; i++, j++) {
            if (gap === 0) {
                dp[i][j] = true; // Single characters are palindromes
            } else if (gap === 1) {
                dp[i][j] = (str[i] === str[j]); // Two characters are palindromes if they are the same
            } else {
                dp[i][j] = (str[i] === str[j] && dp[i + 1][j - 1]); // Check if the substring is a palindrome
            }
 
            if (dp[i][j]) {
                result.add(str.substring(i, j + 1));
            }
        }
    }
 
    return Array.from(result);
}
 
// Main function
const str = "abaaa";
const palindromicSubstrings = findDistinctPalindromicSubstrings(str);
 
console.log("Number of distinct palindromic substrings are: " + palindromicSubstrings.length);
console.log("Distinct palindromic substrings:");
palindromicSubstrings.forEach(substring => {
    console.log(substring);
});

Output

No of distinct palindromic substrings are : 5
a
aa
aaa
aba
b

Time Complexity: O(N^2 * log(N)) since we are iterating through the matrix and while doing so we put elements in set which takes log(N) time
Space Complexity: O(N^2) since we using 2-D array

Method 1:

Step 1: Finding all palindromes using modified Manacher’s algorithm:
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even).
Time complexity for this step is O(n^2)

Step 2: Inserting all the found palindromes in a HashMap:
Insert all the palindromes found from the previous step into a HashMap. Also insert all the individual characters from the string into the HashMap (to generate distinct single letter palindromic sub-strings).
Time complexity of this step is O(n^3) assuming that the hash insert search takes O(1) time. Note that there can be at most O(n^2) palindrome sub-strings of a string. In below C++ code ordered hashmap is used where the time complexity of insert and search is O(Logn). In C++, ordered hashmap is implemented using Red Black Tree.

Step 3: Printing the distinct palindromes and number of such distinct palindromes:
The last step is to print all values stored in the HashMap (only distinct elements will be hashed due to the property of HashMap). The size of the map gives the number of distinct palindromic continuous sub-strings.

Below is the implementation of the above idea.

C++

// C++ program to find all distinct palindrome sub-strings 
// of a given string 
#include <iostream> 
#include <map> 
using namespace std; 
   
// Function to print all distinct palindrome sub-strings of s 
void palindromeSubStrs(string s) 
{ 
    map<string, int> m; 
    int n = s.size(); 
   
    // table for storing results (2 rows for odd- 
    // and even-length palindromes 
    int R[2][n+1]; 
   
    // Find all sub-string palindromes from the given input 
    // string insert 'guards' to iterate easily over s 
    s = "@" + s + "#"; 
   
    for (int j = 0; j <= 1; j++) 
    { 
        int rp = 0;   // length of 'palindrome radius' 
        R[j][0] = 0; 
   
        int i = 1; 
        while (i <= n) 
        { 
            //  Attempt to expand palindrome centered at i 
            while (s[i - rp - 1] == s[i + j + rp]) 
                rp++;  // Incrementing the length of palindromic 
                       // radius as and when we find valid palindrome 
   
            // Assigning the found palindromic length to odd/even 
            // length array 
            R[j][i] = rp; 
            int k = 1; 
            while ((R[j][i - k] != rp - k) && (k < rp)) 
            { 
                R[j][i + k] = min(R[j][i - k],rp - k); 
                k++; 
            } 
            rp = max(rp - k,0); 
            i += k; 
        } 
    } 
   
    // remove 'guards' 
    s = s.substr(1, n); 
   
    // Put all obtained palindromes in a hash map to 
    // find only distinct palindromess 
    m[string(1, s[0])]=1; 
    for (int i = 1; i <= n; i++) 
    { 
        for (int j = 0; j <= 1; j++) 
            for (int rp = R[j][i]; rp > 0; rp--) 
               m[s.substr(i - rp - 1, 2 * rp + j)]=1; 
        m[string(1, s[i])]=1; 
    } 
   
    //printing all distinct palindromes from hash map 
   cout << "Below are " << m.size()-1 
        << " palindrome sub-strings"; 
   map<string, int>::iterator ii; 
   for (ii = m.begin(); ii!=m.end(); ++ii) 
      cout << (*ii).first << endl; 
} 
   
// Driver program 
int main() 
{ 
    palindromeSubStrs("abaaa"); 
    return 0; 
}

Java

// Java program to find all distinct palindrome
// sub-strings of a given string
import java.util.Map;
import java.util.TreeMap;
 
public class GFG 
{     
    // Function to print all distinct palindrome
    // sub-strings of s
    static void palindromeSubStrs(String s)
    {
        //map<string, int> m;
        TreeMap<String , Integer> m = new TreeMap<>();
        int n = s.length();
      
        // table for storing results (2 rows for odd-
        // and even-length palindromes
        int[][] R = new int[2][n+1];
      
        // Find all sub-string palindromes from the 
        // given input string insert 'guards' to 
        // iterate easily over s
        s = "@" + s + "#";
      
        for (int j = 0; j <= 1; j++)
        {
            int rp = 0;   // length of 'palindrome radius'
            R[j][0] = 0;
      
            int i = 1;
            while (i <= n)
            {
                //  Attempt to expand palindrome centered 
                // at i
                while (s.charAt(i - rp - 1) == s.charAt(i + 
                                                j + rp))
                    rp++;  // Incrementing the length of
                           // palindromic radius as and 
                           // when we find valid palindrome
      
                // Assigning the found palindromic length
                // to odd/even length array
                R[j][i] = rp;
                int k = 1;
                while ((R[j][i - k] != rp - k) && (k < rp))
                {
                    R[j][i + k] = Math.min(R[j][i - k], 
                                              rp - k);
                    k++;
                }
                rp = Math.max(rp - k,0);
                i += k;
            }
        }
      
        // remove 'guards'
        s = s.substring(1, s.length()-1);
      
        // Put all obtained palindromes in a hash map to
        // find only distinct palindromess
        m.put(s.substring(0,1), 1);
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= 1; j++)
                for (int rp = R[j][i]; rp > 0; rp--)
                   m.put(s.substring(i - rp - 1,  i - rp - 1
                                       + 2 * rp + j), 1);
            m.put(s.substring(i, i + 1), 1);
        }
      
        // printing all distinct palindromes from 
        // hash map
       System.out.println("Below are " + (m.size())
                           + " palindrome sub-strings");
        
       for (Map.Entry<String, Integer> ii:m.entrySet())
          System.out.println(ii.getKey());
    }
      
    // Driver program
    public static void main(String args[])
    {
        palindromeSubStrs("abaaa");
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program Find all distinct palindromic sub-strings
# of a given string
 
# Function to print all distinct palindrome sub-strings of s
def palindromeSubStrs(s):
    m = dict()
    n = len(s)
 
    # table for storing results (2 rows for odd-
    # and even-length palindromes
    R = [[0 for x in range(n+1)] for x in range(2)]
 
    # Find all sub-string palindromes from the given input
    # string insert 'guards' to iterate easily over s
    s = "@" + s + "#"
 
    for j in range(2):
        rp = 0    # length of 'palindrome radius'
        R[j][0] = 0
 
        i = 1
        while i <= n:
 
            # Attempt to expand palindrome centered at i
            while s[i - rp - 1] == s[i + j + rp]:
                rp += 1 # Incrementing the length of palindromic
                        # radius as and when we find valid palindrome
 
            # Assigning the found palindromic length to odd/even
            # length array
            R[j][i] = rp
            k = 1
            while (R[j][i - k] != rp - k) and (k < rp):
                R[j][i+k] = min(R[j][i-k], rp - k)
                k += 1
            rp = max(rp - k, 0)
            i += k
 
    # remove guards
    s = s[1:len(s)-1]
 
    # Put all obtained palindromes in a hash map to
    # find only distinct palindrome
    m[s[0]] = 1
    for i in range(1,n):
        for j in range(2):
            for rp in range(R[j][i],0,-1):
                m[s[i - rp - 1 : i - rp - 1 + 2 * rp + j]] = 1
        m[s[i]] = 1
 
    # printing all distinct palindromes from hash map
    print ("Below are " + str(len(m)) + " pali sub-strings")
    for i in m:
        print (i)
 
# Driver program
palindromeSubStrs("abaaa")
# This code is contributed by BHAVYA JAIN and ROHIT SIKKA

C#

// C# program to find all distinct palindrome 
// sub-strings of a given string
using System;
using System.Collections.Generic;
 
class GFG 
{
 
    // Function to print all distinct palindrome 
    // sub-strings of s
    public static void palindromeSubStrs(string s) 
    {
        //map<string, int> m;
        Dictionary < string,
        int > m = new Dictionary < string,
        int > ();
        int n = s.Length;
 
        // table for storing results (2 rows for odd- 
        // and even-length palindromes
        int[, ] R = new int[2, n + 1];
 
        // Find all sub-string palindromes from the 
        // given input string insert 'guards' to 
        // iterate easily over s
        s = "@" + s + "#";
        for (int j = 0; j <= 1; j++)
        {
            int rp = 0; // length of 'palindrome radius'
            R[j, 0] = 0;
            int i = 1;
            while (i <= n) 
            {
                 
                // Attempt to expand palindrome centered 
                // at i
                while (s[i - rp - 1] == s[i + j + rp])
 
                // Incrementing the length of 
                // palindromic radius as and 
                // when we find valid palindrome
                rp++;
 
                // Assigning the found palindromic length 
                // to odd/even length array
                R[j, i] = rp;
                int k = 1;
                while ((R[j, i - k] != rp - k) && k < rp)
                {
                    R[j, i + k] = Math.Min(R[j, i - k], rp - k);
                    k++;
                }
                rp = Math.Max(rp - k, 0);
                i += k;
            }
        }
 
        // remove 'guards'
        s = s.Substring(1);
 
        // Put all obtained palindromes in a hash map to 
        // find only distinct palindromess
        if (!m.ContainsKey(s.Substring(0, 1))) 
            m.Add(s.Substring(0, 1), 1);
        else
            m[s.Substring(0, 1)]++;
 
        for (int i = 1; i < n; i++) 
        {
            for (int j = 0; j <= 1; j++)
            for (int rp = R[j, i]; rp > 0; rp--) 
            {
                if (!m.ContainsKey(s.Substring(i - rp - 1, 2 * rp + j))) 
                    m.Add(s.Substring(i - rp - 1, 2 * rp + j), 1);
                else
                    m[s.Substring(i - rp - 1, 2 * rp + j)]++;
            }
 
            if (!m.ContainsKey(s.Substring(i, 1))) 
                m.Add(s.Substring(i, 1), 1);
            else
                m[s.Substring(i, 1)]++;
        }
 
        // printing all distinct palindromes from 
        // hash map
        Console.WriteLine("Below are " + (m.Count));
 
        foreach(KeyValuePair < string, int > ii in m)
        Console.WriteLine(ii.Key);
    }
 
    // Driver Code
    public static void Main(string[] args) 
    {
        palindromeSubStrs("abaaa");
    }
}
 
// This code is contributed by
// sanjeev2552

Javascript

<script>
 
// JavaScript program to find all distinct palindrome sub-strings 
// of a given string 
 
// Function to print all distinct palindrome sub-strings of s 
function palindromeSubStrs(s) 
{ 
    let m = new Map(); 
    let n = s.length; 
   
    // table for storing results (2 rows for odd- 
    // and even-length palindromes 
    let R = new Array(2);
    for(let i = 0; i < 2; i++)
        R[i] = new Array(n + 1); 
   
    // Find all sub-string palindromes from the given input 
    // string insert 'guards' to iterate easily over s 
    s = "@" + s + "#"; 
   
    for (let j = 0; j <= 1; j++) 
    { 
        let rp = 0;   // length of 'palindrome radius' 
        R[j][0] = 0; 
   
        let i = 1; 
        while (i <= n) 
        { 
         
            //  Attempt to expand palindrome centered at i 
            while (s[i - rp - 1] == s[i + j + rp]) 
                rp++;  // Incrementing the length of palindromic 
                       // radius as and when we find valid palindrome 
   
            // Assigning the found palindromic length to odd/even 
            // length array 
            R[j][i] = rp; 
            let k = 1; 
            while ((R[j][i - k] != rp - k) && (k < rp)) 
            { 
                R[j][i + k] = Math.min(R[j][i - k],rp - k); 
                k++; 
            } 
            rp = Math.max(rp - k,0); 
            i += k; 
        } 
    } 
   
    // remove 'guards' 
    s = s.substring(1, n+1); 
   
    // Put all obtained palindromes in a hash map to 
    // find only distinct palindromes
    m.set(`${s[0]}`,1); 
    for (let i = 1; i < n; i++) 
    { 
        for (let j = 0; j <= 1; j++){
            for (let rp = R[j][i]; rp > 0; rp--){ 
               m.set(s.substring(i - rp - 1, i + rp + j-1),1); 
            }
        }
        m.set(`${s[i]}`,1); 
    } 
   
    // printing all distinct palindromes from hash map 
   document.write(`Below are ${m.size} palindrome sub-strings`,"</br>"); 
   for(let [x, y] of m)
      document.write(x,"</br>"); 
} 
   
// Driver program 
palindromeSubStrs("abaaa"); 
 
// This code is contributed by shinjanpatra
</script>

Output:

 Below are 5 palindrome sub-strings
a
aa
aaa
aba
b

Method 2 :

String length – N

Step 1 : Find all the palindromic sub-strings

First for every sub-string check if it is palindrome or not using dynamic programming like this – https://www.geeksforgeeks.org/count-palindrome-sub-strings-string/

Time complexity – O(N²) and Space complexity – O(N²)

Step 2 : Remove duplicate palindromes

For every index starting from index 0 we will use KMP algorithm and check if prefix and suffix is same and is palindrome then we will put 0 the dp array for that suffix sub-string

Time complexity O(N²) and Space complexity O(N) for KMP array

Step 3 : Print the distinct palindromes and number of such palindromes

For every sub-string check if it is present in dp array (i.e dp[i][j] == true) and print it.

Time complexity O(N²) and Space complexity O(N)

Overall Time complexity – O(N²)

Overall Space complexity – O(N²)

Below is the implementation of the above idea.

C++

// C++ program to find all distinct palindrome sub-strings
// of a given string
#include <iostream>
#include <vector>
using namespace std;
 
int solve(string s)
{
    int n = s.size();
    // dp array to store whether a substring is palindrome
    // or not using dynamic programming we can solve this
    // in O(N^2)
    // dp[i][j] will be true (1) if substring (i, j) is
    // palindrome else false (0)
    vector<vector<bool> > dp(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        // base case every char is palindrome
        dp[i][i] = 1;
        // check for every substring of length 2
        if (i < n && s[i] == s[i + 1]) {
            dp[i][i + 1] = 1;
        }
    }
    // check every substring of length greater than 2 for
    // palindrome
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            if (s[i] == s[i + (len - 1)]
                && dp[i + 1][i + (len - 1) - 1]) {
                dp[i][i + (len - 1)] = true;
            }
        }
    }
 
    //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
    // here we will apply kmp algorithm for substrings
    // starting from i = 0 to n-1 when we will find prefix
    // and suffix of a substring to be equal and it is
    // palindrome we will make dp[i][j] for that suffix to be
    // false which means it is already added in the prefix
    // and we should not count it anymore.
    vector<int> kmp(n, 0);
    for (int i = 0; i < n; i++) {
        // starting kmp for every i from 0 to n-1
        int j = 0, k = 1;
        while (k + i < n) {
            if (s[j + i] == s[k + i]) {
                // make suffix to be false
                // if this suffix is palindrome then it is
                // already included in prefix
                dp[k + i - j][k + i] = false;
                kmp[k++] = ++j;
            }
            else if (j > 0) {
                j = kmp[j - 1];
            }
            else {
                kmp[k++] = 0;
            }
        }
    }
    //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
    int count = 0;
    for (int i = 0; i < n; i++) {
        string str;
        for (int j = i; j < n; j++) {
            str += s[j];
            if (dp[i][j]) {
                // count number of resultant distinct
                // substrings and print  that substring
                count++;
                cout << str << '\n';
            }
        }
    }
    cout << "Total number of distinct palindromes is "
         << count << '\n';
      return 0;
}
 
// Driver code starts
// This code is contributed by Aditya Anand
int main()
{
    string s1 = "abaaa", s2 = "aaaaaaaaaa";
    solve(s1);
    solve(s2);
    return 0;
}
// Driver code ends

Java

// Java program to find all distinct palindrome sub-strings
// of a given string
import java.util.*;
 
class GFG
{
   
  // Driver code starts
  public static void main(String[] args)
  {
    String s1 = "abaaa", s2 = "aaaaaaaaaa";
    solve(s1);
    solve(s2);
  }
 
  public static int solve(String s)
  {
    int n = s.length();
     
    // dp array to store whether a substring is
    // palindrome or not using dynamic programming we
    // can solve this in O(N^2) dp[i][j] will be true
    // (1) if substring (i, j) is palindrome else false
    // (0)
    boolean[][] dp = new boolean[n][n];
    for (int i = 0; i < n; i++) 
    {
       
      // base case every char is palindrome
      dp[i][i] = true;
       
      // check for every substring of length 2
      if (i < n - 1
          && s.charAt(i) == s.charAt(i + 1)) {
        dp[i][i + 1] = true;
      }
    }
     
    // check every substring of length greater than 2
    // for palindrome
    for (int len = 3; len <= n; len++) {
      for (int i = 0; i + len - 1 < n; i++) {
        if (s.charAt(i) == s.charAt(i + (len - 1))
            && dp[i + 1][i + (len - 1) - 1]) {
          dp[i][i + (len - 1)] = true;
        }
      }
    }
 
    //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
    // here we will apply kmp algorithm for substrings
    // starting from i = 0 to n-1 when we will find
    // prefix and suffix of a substring to be equal and
    // it is palindrome we will make dp[i][j] for that
    // suffix to be false which means it is already
    // added in the prefix and we should not count it
    // anymore.
    int[] kmp = new int[n];
    for (int i = 0; i < n; i++) 
    {
       
      // starting kmp for every i from 0 to n-1
      int j = 0, k = 1;
      while (k + i < n) {
        if (s.charAt(j + i) == s.charAt(k + i))
        {
           
          // make suffix to be false
          // if this suffix is palindrome then it
          // is already included in prefix
          dp[k + i - j][k + i] = false;
          kmp[k++] = ++j;
        }
        else if (j > 0) {
          j = kmp[j - 1];
        }
        else {
          kmp[k++] = 0;
        }
      }
    }
    //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
    int count = 0;
    for (int i = 0; i < n; i++) {
      String str = "";
      for (int j = i; j < n; j++) {
        str += s.charAt(j);
        if (dp[i][j])
        {
           
          // count number of resultant distinct
          // substrings and print  that substring
          count++;
          System.out.println(str);
        }
      }
    }
    System.out.println(
      "Total number of distinct palindromes is "
      + count);
    return 0;
  }
}
 
// This code is contributed by kdheeraj.

Python3

# Python3 program to find all distinct palindrome sub-strings
# of a given string
def solve(s):
    n = len(s)
     
    # dp array to store whether a substring is palindrome
    # or not using dynamic programming we can solve this
    # in O(N^2)
    # dp[i][j] will be true (1) if substring (i, j) is
    # palindrome else false (0)
    dp = [[False for j in range(n)] for i in range(n)]
    for i in range(n):
       
        # base case every char is palindrome
        dp[i][i] = True
         
        # check for every substring of length 2
        if i < n-1 and s[i] == s[i+1]:
            dp[i][i+1] = True
             
    # check every substring of length greater than 2 for
    # palindrome
    for lenk in range(3, n+1):
        for i in range(n-lenk+1):
            if s[i] == s[i+lenk-1] and dp[i+1][i+lenk-2]:
                dp[i][i+lenk-1] = True
                 
    # here we will apply kmp algorithm for substrings
    # starting from i = 0 to n-1 when we will find prefix
    # and suffix of a substring to be equal and it is
    # palindrome we will make dp[i][j] for that suffix to be
    # false which means it is already added in the prefix
    # and we should not count it anymore.
    kmp = [0]*n
    for i in range(n):
       
        # starting kmp for every i from 0 to n-1
        j, k = 0, 1
        while k+i < n:
            if s[j+i] == s[k+i]:
               
                # make suffix to be false
                # if this suffix is palindrome then it is
                # already included in prefix
                dp[k+i-j][k+i] = False
                kmp[k] = j+1
                k += 1
                j += 1
            elif j > 0:
                j = kmp[j-1]
            else:
                kmp[k] = 0
                k += 1
    count = 0
    for i in range(n):
        str = ""
        for j in range(i, n):
            str += s[j]
            if dp[i][j]:
                # count number of resultant distinct
                # substrings and print  that substring
                count += 1
                print(str)
    print("Total number of distinct palindromes is", count)
    return 0
 
# Driver code starts
 
if __name__ == "__main__":
    s1 = "abaaa"
    s2 = "aaaaaaaaaa"
    solve(s1)
    solve(s2)
 
    # This code is contributed by lokeshpotta20.

C#

using System;
class GFG
{
  static int solve(string s)
  {
    int n = s.Length;
 
    // dp array to store whether a substring is palindrome
    // or not using dynamic programming we can solve this
    // in O(N^2)
    // dp[i][j] will be true (1) if substring (i, j) is
    // palindrome else false (0)
    bool[][] dp = new bool[n][];
    for (int i = 0; i < n; i++)
    {
      dp[i] = new bool[n];
 
      // base case every char is palindrome
      dp[i][i] = true;
 
      // check for every substring of length 2
      if (i < n - 1 && s[i] == s[i + 1])
      {
        dp[i][i + 1] = true;
      }
    }
 
    // check every substring of length greater than 2 for
    // palindrome
    for (int len = 3; len <= n; len++)
    {
      for (int i = 0; i + len - 1 < n; i++)
      {
        if (s[i] == s[i + len - 1] && dp[i + 1][i + len - 2])
        {
          dp[i][i + len - 1] = true;
        }
      }
    }
 
    //--------------------------------*
    // here we will apply kmp algorithm for substrings
    // starting from i = 0 to n-1 when we will find prefix
    // and suffix of a substring to be equal and it is
    // palindrome we will make dp[i][j] for that suffix to be
    // false which means it is already added in the prefix
    // and we should not count it anymore.
    int[] kmp = new int[n];
    for (int i = 0; i < n; i++)
    {
 
      // starting kmp for every i from 0 to n-1
      int j = 0, k = 1;
      while (k + i < n)
      {
        if (s[j + i] == s[k + i])
        {
 
          // make suffix to be false
          // if this suffix is palindrome then it is
          // already included in prefix
          dp[k + i - j][k + i] = false;
          kmp[k++] = ++j;
        }
        else if (j > 0)
        {
          j = kmp[j - 1];
        }
        else
        {
          kmp[k++] = 0;
        }
      }
    }
    //---------------------------------
    int count = 0;
    for (int i = 0; i < n; i++)
    {
      string str = "";
      for (int j = i; j < n; j++)
      {
        str += s[j];
        if (dp[i][j])
        {
 
          // count number of resultant distinct
          // substrings and print that substring
          count++;
          Console.WriteLine(str);
        }
      }
 
    }
    Console.WriteLine("Total number of distinct palindromes is "+ count);
 
    return count;
  }
 
  // Driver code starts
  static void Main(string[] args)
  {
    string s1 = "abaaa";
    string s2 = "aaaaaaaaaa";
    solve(s1);
    solve(s2);
  }
 
  // Driver code ends
}
 
// This code is contributed by imruhrbf8.

Javascript

// Javascript program to find all distinct palindrome sub-strings
// of a given string
function solve(s)
{
    let n = s.length;
     
    // dp array to store whether a substring is palindrome
    // or not using dynamic programming we can solve this
    // in O(N^2)
    // dp[i][j] will be true (1) if substring (i, j) is
    // palindrome else false (0)
    let dp = new Array(n);
    for(let i = 0; i < n; i++)
        dp[i] = new Array(n).fill(0);
    for (let i = 0; i < n; i++) 
    {
     
        // base case every char is palindrome
        dp[i][i] = 1;
         
        // check for every substring of length 2
        if (i < n && s[i] == s[i + 1]) {
            dp[i][i + 1] = 1;
        }
    }
     
    // check every substring of length greater than 2 for
    // palindrome
    for (let len = 3; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            if (s[i] == s[i + (len - 1)]
                && dp[i + 1][i + (len - 1) - 1]) {
                dp[i][i + (len - 1)] = true;
            }
        }
    }
 
    //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
    // here we will apply kmp algorithm for substrings
    // starting from i = 0 to n-1 when we will find prefix
    // and suffix of a substring to be equal and it is
    // palindrome we will make dp[i][j] for that suffix to be
    // false which means it is already added in the prefix
    // and we should not count it anymore.
    let kmp=new Array(n).fill(0);
    for (let i = 0; i < n; i++)
    {
 
        // starting kmp for every i from 0 to n-1
        let j = 0, k = 1;
        while (k + i < n) 
        {
            if (s[j + i] == s[k + i])
            {
             
                // make suffix to be false
                // if this suffix is palindrome then it is
                // already included in prefix
                dp[k + i - j][k + i] = false;
                kmp[k++] = ++j;
            }
            else if (j > 0) {
                j = kmp[j - 1];
            }
            else {
                kmp[k++] = 0;
            }
        }
    }
     
    //*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
    let count = 0;
    for (let i = 0; i < n; i++) {
        let str="";
        for (let j = i; j < n; j++) {
            str += s[j];
            if (dp[i][j])
            {
             
                // count number of resultant distinct
                // substrings and print  that substring
                count++;
                console.log(str);
            }
        }
    }
    console.log("Total number of distinct palindromes is "
        + count);
}
 
// Driver code starts
let s1 = "abaaa", s2 = "aaaaaaaaaa";
solve(s1);
solve(s2);
 
// This code is contributed by ratiagrawal.

Output

a
aba
b
aa
aaa
Total number of distinct palindromes is 5
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
Total number of distinct palindromes is 10

Approach:

This code uses an unordered set to store distinct palindromes and avoids using dynamic programming or the KMP algorithm. It first checks for odd-length palindromes and then even-length palindromes by expanding from each character as a center. Finally, it prints all distinct palindromes and the total count.

C++

#include <iostream>
#include <unordered_set>
using namespace std;
 
void findAllPalindromes(const string& s) {
    int n = s.size();
    unordered_set<string> palindromes;
 
    // Check for odd length palindromes
    for (int i = 0; i < n; i++) {
        int left = i, right = i;
        while (left >= 0 && right < n && s[left] == s[right]) {
            palindromes.insert(s.substr(left, right - left + 1));
            left--;
            right++;
        }
    }
 
    // Check for even length palindromes
    for (int i = 0; i < n - 1; i++) {
        int left = i, right = i + 1;
        while (left >= 0 && right < n && s[left] == s[right]) {
            palindromes.insert(s.substr(left, right - left + 1));
            left--;
            right++;
        }
    }
 
    // Print all distinct palindromes
    for (const auto& palindrome : palindromes) {
        cout << palindrome << endl;
    }
 
    cout << "Total number of distinct palindromes is " << palindromes.size() << endl;
}
 
int main() {
    string s1 = "abaaa", s2 = "aaaaaaaaaa";
    findAllPalindromes(s1);
    findAllPalindromes(s2);
    return 0;
}

Java

import java.util.HashSet;
 
class Main {
 
    // Function to find all distinct palindromes
    static void findAllPalindromes(String s)
    {
        int n = s.length();
        HashSet<String> palindromes = new HashSet<>();
 
        // Check for odd length palindromes
        for (int i = 0; i < n; i++) {
            int left = i, right = i;
            while (left >= 0 && right < n
                   && s.charAt(left) == s.charAt(right)) {
                palindromes.add(
                    s.substring(left, right + 1));
                left--;
                right++;
            }
        }
 
        // Check for even length palindromes
        for (int i = 0; i < n - 1; i++) {
            int left = i, right = i + 1;
            while (left >= 0 && right < n
                   && s.charAt(left) == s.charAt(right)) {
                palindromes.add(
                    s.substring(left, right + 1));
                left--;
                right++;
            }
        }
 
        // Print all distinct palindromes
        for (String palindrome : palindromes) {
            System.out.println(palindrome);
        }
 
        System.out.println(
            "Total number of distinct palindromes is "
            + palindromes.size());
    }
 
    public static void main(String[] args)
    {
        String s1 = "abaaa";
        String s2 = "aaaaaaaaaa";
 
        // Function calls
        findAllPalindromes(s1);
        findAllPalindromes(s2);
    }
}

Python

def find_all_palindromes(s):
    n = len(s)
    palindromes = set()
 
    # Check for odd length palindromes
    for i in range(n):
        left = right = i
        while left >= 0 and right < n and s[left] == s[right]:
            palindromes.add(s[left:right + 1])
            left -= 1
            right += 1
 
    # Check for even length palindromes
    for i in range(n - 1):
        left = i
        right = i + 1
        while left >= 0 and right < n and s[left] == s[right]:
            palindromes.add(s[left:right + 1])
            left -= 1
            right += 1
 
    # Print all distinct palindromes
    for palindrome in palindromes:
        print(palindrome)
 
    print("Total number of distinct palindromes is {}".format(len(palindromes)))
 
 
# Example usage:
s1 = "abaaa"
s2 = "aaaaaaaaaa"
find_all_palindromes(s1)
find_all_palindromes(s2)

C#

using System;
using System.Collections.Generic;
 
class Program {
    static void FindAllPalindromes(string s)
    {
        int n = s.Length;
        HashSet<string> palindromes = new HashSet<string>();
 
        // Check for odd length palindromes
        for (int i = 0; i < n; i++) {
            int left = i, right = i;
            while (left >= 0 && right < n
                   && s[left] == s[right]) {
                palindromes.Add(
                    s.Substring(left, right - left + 1));
                left--;
                right++;
            }
        }
 
        // Check for even length palindromes
        for (int i = 0; i < n - 1; i++) {
            int left = i, right = i + 1;
            while (left >= 0 && right < n
                   && s[left] == s[right]) {
                palindromes.Add(
                    s.Substring(left, right - left + 1));
                left--;
                right++;
            }
        }
 
        // Print all distinct palindromes
        foreach(string palindrome in palindromes)
        {
            Console.WriteLine(palindrome);
        }
 
        Console.WriteLine(
            "Total number of distinct palindromes is "
            + palindromes.Count);
    }
 
    static void Main()
    {
        string s1 = "abaaa";
        string s2 = "aaaaaaaaaa";
        FindAllPalindromes(s1);
        FindAllPalindromes(s2);
    }
}

Javascript

function findAllPalindromes(s) {
    let n = s.length;
    let palindromes = new Set();
 
    // Check for odd length palindromes
    for (let i = 0; i < n; i++) {
        let left = i, right = i;
        while (left >= 0 && right < n && s[left] == s[right]) {
            palindromes.add(s.substring(left, right + 1));
            left--;
            right++;
        }
    }
 
    // Check for even length palindromes
    for (let i = 0; i < n - 1; i++) {
        let left = i, right = i + 1;
        while (left >= 0 && right < n && s[left] == s[right]) {
            palindromes.add(s.substring(left, right + 1));
            left--;
            right++;
        }
    }
 
    // Prlet all distinct palindromes
    for (let palindrome of palindromes) {
        console.log(palindrome);
    }
 
    console.log("Total number of distinct palindromes is " + palindromes.size);
 
}
 
let s1 = "abaaa", s2 = "aaaaaaaaaa";
findAllPalindromes(s1);
findAllPalindromes(s2);

Output

aa
aaa
aba
b
a
Total number of distinct palindromes is 5
aaaaaaaaaa
aaaaaaaa
aaaaaa
aaaa
aaaaaaa
aa
aaaaa
aaa
aaaaaaaaa
a
Total number of distinct palindromes is 10

Time complexity: O(N^3)
Space complexity: O(N)

Similar Problem:
Count All Palindrome Sub-Strings in a String
This article is contributed by Vignesh Narayanan and Sowmya Sampath.

Suggest improvement

OLA Interview Experience | Set 11 ( For Internship)

Find a common element in all rows of a given row-wise sorted matrix

Share your thoughts in the comments

Find all distinct palindromic sub-strings of a given string

BRUTE APPROACH

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?