Given a string, find all possible palindromic substrings in it.
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(n3).
We can solve this problem in O(n2) 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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#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; } |
Output:
e l g o oo goog
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
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); } } |
Output:
[oo, goog, e, g, l, o]
(2 votes, average: 5.00 out of 5)
Loading...
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 🙂
Leave a Reply
“The complexity would be exponential.” Nope.
Thanks Eric for bringing this to our notice. We have updated the complexity.
This is beautiful!
here is the simple code in JAVA
https://stackoverflow.com/a/46752568/8778562