Given an array of strings arr[] containing N words, the task is to print all possible palindromic string by combining any two strings from the given array.
Examples:
Input: arr[] = [“geekf”, “neveropen”, “or”, “keeg”, “abc”, “ba”]
Output: [“geekfkeeg”, “neveropenkeeg”, “abcba”]
Explanation:
Below pairs forms the palindromic string on combining:
1. “geekf” + “keeg” = “geekfkeeg”
2. “neveropen” + “keeg” = “neveropenkeeg”
3. “abc” + “ba” = “abcba”Input: arr[] = [“dcb”, “yz”, “xy”, “efg”, “yx”]
Output: [“xyyx”, “yxxy”]
Explanation:
1. “xy” + “yz” = “xyyz”
2. “yx” + “xy” = “yxxy”
Naive Approach: The naive approach is to iterate all possible pairs in the given array of strings and check whether concatenation of the string forms palindromic or not. If yes then print that pair and check for the next pairs.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using Hashing. Below are the steps:
- Store all the words in a Map with words as keys and indices as values.
- For each word(say str) in the arr[] break the string into string s1 and s2 such that s1 + s2 = str.
- After the above step there arise two cases:
- Case 1: If s1 is a palindromic string and the reverse of s2 is present in the hash-map then we get the required pair (reverse of s2 + current word).
- Case 2: If s2 is a palindromic string and if reverse s1 is present in the hash-map then we get a pair (current word + reverse of s1).
- Repeat the above steps for all the strings in the array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether the string// word is palindrome or notbool ispalin(string word){ if (word.length() == 1 || word.empty()) { return true; } int l = 0; int r = word.length() - 1; // Iterate word while (l <= r) { if (word[l] != word[r]) { return false; } l++; r--; } return true;}// Function to find the palindromicPairsvector<string>palindromicPairs(vector<string>& words){ vector<string> output; if (words.size() == 0 || words.size() == 1) { return output; } // Insert all the strings with // their indices in the hash map unordered_map<string, int> mp; for (int i = 0; i < words.size(); i++) { mp[words[i]] = i; } // Iterate over all the words for (int i = 0; i < words.size(); i++) { // If the word is empty then // we simply pair it will all the // words which are palindrome // present in the array // except the word itself if (words[i].empty()) { for (auto x : mp) { if (x.second == i) { continue; } if (ispalin(x.first)) { output.push_back(x.first); } } } // Create all possible substrings // s1 and s2 for (int j = 0; j < words[i].length(); j++) { string s1 = words[i].substr(0, j + 1); string s2 = words[i].substr(j + 1); // Case 1 // If s1 is palindrome and // reverse of s2 is // present in hashmap at // index other than i if (ispalin(s1)) { reverse(s2.begin(), s2.end()); string temp = s2; if (mp.count(s2) == 1 && mp[s2] != i) { string ans = s2 + words[i]; output.push_back(ans); } s2 = temp; } // Case 2 // If s2 is palindrome and // reverse of s1 is // present in hashmap // at index other than i if (ispalin(s2)) { string temp = s1; reverse(s1.begin(), s1.end()); if (mp.count(s1) == 1 && mp[s1] != i) { string ans = words[i] + s1; output.push_back(ans); } s1 = temp; } } } // Return output return output;}// Driver Codeint main(){ vector<string> words; // Given array of words words = { "geekf", "neveropen", "or", "keeg", "abc", "ba" }; // Function call vector<string> result = palindromicPairs(words); // Print the palindromic strings // after combining them for (auto x : result) { cout << x << endl; } return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Function to check whether the string // word is palindrome or not static boolean ispalin(String word) { if (word.length() == 1 || word.length() == 0) { return true; } int l = 0; int r = word.length() - 1; // Iterate word while (l <= r) { if (word.charAt(l) != word.charAt(r)) { return false; } l++; r--; } return true; } // Function to find the palindromicPairs static Vector<String> palindromicPairs(String[] words) { Vector<String> output = new Vector<String>(); if (words.length == 0 || words.length == 1) { return output; } // Insert all the strings with // their indices in the hash map HashMap<String, Integer> mp = new HashMap<>(); for (int i = 0; i < words.length; i++) { mp.put(words[i], i); } // Iterate over all the words for(int i = 0; i < words.length; i++) { // If the word is empty then // we simply pair it will all the // words which are palindrome // present in the array // except the word itself if ((words[i]).length() == 0) { for(Map.Entry<String, Integer> key : mp.entrySet()) { if (key.getValue() == i) { continue; } if (ispalin(key.getKey())) { output.add(key.getKey()); } } } // Create all possible substrings // s1 and s2 for(int j = 0; j < words[i].length(); j++) { String s1 = words[i].substring(0, j + 1); String s2 = words[i].substring(j + 1); // Case 1 // If s1 is palindrome and // reverse of s2 is // present in hashmap at // index other than i if (ispalin(s1)) { StringBuffer arr = new StringBuffer(s2); arr.reverse(); s2 = new String(arr); String temp = s2; if (mp.containsKey(s2) && mp.get(s2) != i) { String ans = s2 + words[i]; output.add(ans); } s2 = temp; } // Case 2 // If s2 is palindrome and // reverse of s1 is // present in hashmap // at index other than i if (ispalin(s2)) { String temp = s1; StringBuffer arr = new StringBuffer(s1); arr.reverse(); s1 = new String(arr); if (mp.containsKey(s1) && mp.get(s1) != i) { String ans = words[i] + s1; output.add(ans); } s1 = temp; } } } // Return output return output; } public static void main(String[] args) { String[] words = { "geekf", "neveropen", "or", "keeg", "abc", "ba" }; // Function call Vector<String> result = palindromicPairs(words); // Print the palindromic strings // after combining them for(String x : result) System.out.println(x); }}// This code is contributed by mukesh07. |
Python3
# Python3 program for the above approach# Function to check whether the string# word is palindrome or notdef ispalin(word): if (len(word) == 1 or len(word)): return True l = 0 r = len(word) - 1 # Iterate word while (l <= r): if (word[l] != word[r]): return False l+= 1 r-= 1 return True# Function to find the palindromicPairsdef palindromicPairs(words): output = [] if (len(words) == 0 or len(words) == 1): return output # Insert all the strings with # their indices in the hash map mp = {} for i in range(len(words)): mp[words[i]] = i # Iterate over all the words for i in range(len( words)): # If the word is empty then # we simply pair it will all the # words which are palindrome # present in the array # except the word itself if (len(words[i]) == 0): for x in mp: if (mp[x] == i): continue if (ispalin(x)): output.append(x) # Create all possible substrings # s1 and s2 for j in range (len(words[i])): s1 = words[i][0 : j + 1] s2 = words[i][j + 1 : ] # Case 1 # If s1 is palindrome and # reverse of s2 is # present in hashmap at # index other than i if (ispalin(s1)): p = list(s2) p.reverse() s2 = ''.join(p) temp = s2; if (s2 in mp and mp[s2] != i): ans = s2 + words[i] output.append(ans) s2 = temp # Case 2 # If s2 is palindrome and # reverse of s1 is # present in hashmap # at index other than i if (ispalin(s2)): temp = s1 p = list(s1) p.reverse() s1 = ''.join(p) if (s1 in mp and mp[s1] != i): ans = words[i] + s1 output.append(ans) s1 = temp # Return output return output# Driver Codeif __name__ == "__main__": # Given array of words words = [ "geekf", "neveropen", "or", "keeg", "abc", "ba" ] # Function call result = palindromicPairs(words); # Print the palindromic strings # after combining them for x in result: print(x) # This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to check whether the string // word is palindrome or not static bool ispalin(string word) { if (word.Length == 1 || word.Length == 0) { return true; } int l = 0; int r = word.Length - 1; // Iterate word while (l <= r) { if (word[l] != word[r]) { return false; } l++; r--; } return true; } // Function to find the palindromicPairs static List<string> palindromicPairs(string[] words) { List<string> output = new List<string>(); if (words.Length == 0 || words.Length == 1) { return output; } // Insert all the strings with // their indices in the hash map Dictionary<string, int> mp = new Dictionary<string, int>(); for (int i = 0; i < words.Length; i++) { mp[words[i]] = i; } // Iterate over all the words for(int i = 0; i < words.Length; i++) { // If the word is empty then // we simply pair it will all the // words which are palindrome // present in the array // except the word itself if (words[i].Length == 0) { foreach(KeyValuePair<string, int> key in mp) { if (key.Value == i) { continue; } if (ispalin(key.Key)) { output.Add(key.Key); } } } // Create all possible substrings // s1 and s2 for(int j = 0; j < words[i].Length; j++) { string s1 = words[i].Substring(0, j + 1); string s2 = words[i].Substring(j + 1); // Case 1 // If s1 is palindrome and // reverse of s2 is // present in hashmap at // index other than i if (ispalin(s1)) { char[] arr = s2.ToCharArray(); Array.Reverse(arr); s2 = new string(arr); string temp = s2; if (mp.ContainsKey(s2) && mp[s2] != i) { string ans = s2 + words[i]; output.Add(ans); } s2 = temp; } // Case 2 // If s2 is palindrome and // reverse of s1 is // present in hashmap // at index other than i if (ispalin(s2)) { string temp = s1; char[] arr = s1.ToCharArray(); Array.Reverse(arr); s1 = new string(arr); if (mp.ContainsKey(s1) && mp[s1] != i) { string ans = words[i] + s1; output.Add(ans); } s1 = temp; } } } // Return output return output; } static void Main() { string[] words = { "geekf", "neveropen", "or", "keeg", "abc", "ba" }; // Function call List<string> result = palindromicPairs(words); // Print the palindromic strings // after combining them foreach(string x in result) { Console.WriteLine(x); } }}// This code is contributed by rameshtravel07. |
Javascript
<script>// Javascript program for the above approach// Function to check whether the string// word is palindrome or notfunction ispalin(word){ if (word.length == 1 || word.length == 0) { return true; } let l = 0; let r = word.length - 1; // Iterate word while (l <= r) { if (word[l] != word[r]) { return false; } l++; r--; } return true;}// Function to find the palindromicPairsfunction palindromicPairs(words){ let output = []; if (words.length == 0 || words.length == 1) { return output; } // Insert all the strings with // their indices in the hash map let mp = new Map(); for(let i = 0; i < words.length; i++) { mp.set(words[i],i); } // Iterate over all the words for(let i = 0; i < words.length; i++) { // If the word is empty then // we simply pair it will all the // words which are palindrome // present in the array // except the word itself if (words[i].length == 0) { for(let [key, value] of mp.entries()) { if (value == i) { continue; } if (ispalin(key)) { output.push(key); } } } // Create all possible substrings // s1 and s2 for(let j = 0; j < words[i].length; j++) { let s1 = words[i].substring(0, j + 1); let s2 = words[i].substring(j + 1); // Case 1 // If s1 is palindrome and // reverse of s2 is // present in hashmap at // index other than i if (ispalin(s1)) { s2 = s2.split("").reverse().join(""); let temp = s2; if (mp.has(s2) && mp.get(s2) != i) { let ans = s2 + words[i]; output.push(ans); } s2 = temp; } // Case 2 // If s2 is palindrome and // reverse of s1 is // present in hashmap // at index other than i if (ispalin(s2)) { let temp = s1; s1 = s1.split("").reverse().join(""); if (mp.has(s1) && mp.get(s1) != i) { let ans = words[i] + s1; output.push(ans); } s1 = temp; } } } // Return output return output;}// Driver Codelet words; // Given array of wordswords = [ "geekf", "neveropen", "or", "keeg", "abc", "ba" ];// Function calllet result = palindromicPairs(words);// Print the palindromic strings// after combining themfor(let i = 0; i < result.length; i++){ document.write(result[i] + " <br>");}// This code is contributed by avanitrachhadiya2155</script> |
Output:
geekfkeeg neveropenkeeg abcba
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
