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]

1 Star 2 Stars 3 Stars 4 Stars 5 Stars (5 votes, average: 5.00 out of 5)

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂