Find all Possible Palindromic Substrings in a String

Given a string, find all possible palindromic substrings in it.

For example,

Input: str = google

Output: e l g o oo goog

A simple solution would be to generate all substrings of the given string and print substrings that are palindrome. The complexity of this solution would be O(n³).

We can solve this problem in O(n²) time and O(1) space. The idea is inspired from Longest Palindromic Substring problem. For each character in the given string, we consider it as mid point of a palindrome and expand in both directions to find all palindromes that have it as mid-point. For even length palindrome, we consider every adjacent pair of characters as mid point. We use a set to store all unique palindromic substrings.

Below is C++ and Java implementation of the idea –

C++

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

// expand in both directions of low and high to find all palindromes
void expand(string str, int low, int high, auto &set)
{
	// run till str[low.high] is a palindrome
	while (low >= 0 && high < str.length()
			&& str[low] == str[high])
	{
		// push all palindromes into the set
		set.insert(str.substr(low, high - low + 1));

		// expand in both directions
		low--, high++;
	}
}

// Function to find all unique palindromic substrings of given string
void allPalindromicSubstrings(string str)
{
	// create an empty set to store all unique palindromic substrings
	unordered_set<string> set;

	for (int i = 0; i < str.length(); i++)
	{
		// find all odd length palindrome with str[i] as mid point
		expand(str, i, i, set);
	
		// find all even length palindrome with str[i] and str[i+1] as
		// its mid points
		expand(str, i, i + 1, set);
	}

	// print all unique palindromic substrings
	for (auto i : set)
		cout << i << " ";
}

// main function
int main()
{
	string str = "google";

	allPalindromicSubstrings(str);

	return 0;
}

#include <iostream>

#include <string>

#include <unordered_set>

using namespace std;

// expand in both directions of low and high to find all palindromes

void expand(string str, int low, int high, auto &set)

{

// run till str[low.high] is a palindrome

while (low >= 0 && high < str.length()

&& str[low] == str[high])

{

// push all palindromes into the set

set.insert(str.substr(low, high - low + 1));

// expand in both directions

low--, high++;

}

// Function to find all unique palindromic substrings of given string

void allPalindromicSubstrings(string str)

{

// create an empty set to store all unique palindromic substrings

unordered_set<string> set;

for (int i = 0; i < str.length(); i++)

{

// find all odd length palindrome with str[i] as mid point

expand(str, i, i, set);

// find all even length palindrome with str[i] and str[i+1] as

// its mid points

expand(str, i, i + 1, set);

}

// print all unique palindromic substrings

for (auto i : set)

cout << i << " ";

}

// main function

int main()

{

string str = "google";

allPalindromicSubstrings(str);

return 0;

}

Download Run Code

Output:

e l g o oo goog

Java

import java.util.HashSet;
import java.util.Set;

class PalindromicSubStrings
{
	// expand in both directions of low and high to find all palindromes
	public static void expand(String str, int low, int high, Set<String> set)
	{
		// run till str[low.high] is a palindrome
		while (low >= 0 && high < str.length()
				&& str.charAt(low) == str.charAt(high))
		{
			// push all palindromes into the set
			set.add(str.substring(low, high + 1));

			// expand in both directions
			low--;
			high++;
		}
	}

	// Function to find all unique palindromic substrings of given string
	public static void allPalindromicSubStrings(String str)
	{
		// create an empty set to store all unique palindromic substrings
		Set<String> set = new HashSet<>();

		for (int i = 0; i < str.length(); i++)
		{
			// find all odd length palindrome with str[i] as mid point
			expand(str, i, i, set);

			// find all even length palindrome with str[i] and str[i+1]
			// as its mid points
			expand(str, i, i + 1, set);
		}

		// print all unique palindromic substrings
		System.out.print(set);
	}

	public static void main(String[] args)
	{
		String str = "google";

		allPalindromicSubStrings(str);
	}
}

import java.util.HashSet;

import java.util.Set;

class PalindromicSubStrings

{

// expand in both directions of low and high to find all palindromes

public static void expand(String str, int low, int high, Set<String> set)

{

// run till str[low.high] is a palindrome

while (low >= 0 && high < str.length()

&& str.charAt(low) == str.charAt(high))

{

// push all palindromes into the set

set.add(str.substring(low, high + 1));

// expand in both directions

low--;

high++;

}

// Function to find all unique palindromic substrings of given string

public static void allPalindromicSubStrings(String str)

{

// create an empty set to store all unique palindromic substrings

Set<String> set = new HashSet<>();

for (int i = 0; i < str.length(); i++)

{

// find all odd length palindrome with str[i] as mid point

expand(str, i, i, set);

// find all even length palindrome with str[i] and str[i+1]

// as its mid points

expand(str, i, i + 1, set);

}

// print all unique palindromic substrings

System.out.print(set);

}

public static void main(String[] args)

{

String str = "google";

allPalindromicSubStrings(str);

}

Download Run Code

Output:

[oo, goog, e, g, l, o]

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂