Given an array of strings arr[], the task is to count the pair of strings whose concatenation of substrings form a palindrome.
Examples:
Input: arr[] = {“gfg”, “gfg”}
Output: 1
Explanation:
One possible way of choosing s1 and s2 is s1 = “gf”, s2 = “g” such that s1 + s2 i.e “gfg” is a palindrome.
Input: arr[] = {“abc”, B = “def”}
Output: 0
Approach: The key observation in the problem is if both strings have at least one common character let’s say ‘c’ then we can form a palindromic string. Therefore, check for all the pairs in the array that there is a common character in the string or not.
Below is the implementation of the above approach:
C++
// C++ implementation to count of // palindromic Palindromic Substrings// that can be formed from the array#include<bits/stdc++.h> using namespace std; // Function to to check if possible// to make palindromic substringbool isPossible(string A, string B) { sort(B.begin(),B.end()); int c=0; for(int i = 0; i < (int)A.size(); i++) if(binary_search(B.begin(),B.end(),A[i])) return true; return false;} // Function to count of Palindromic Substrings// that can be formed from the array.int countPalindromicSubstrings(string s[], int n){ // variable to store count int count = 0; // Traverse through all the pairs // in the array for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++) if(isPossible(s[i], s[j])) count++; } return count;}// Driver Code int main() { string arr[] = { "gfg", "gfg" }; int n = 2; cout << countPalindromicSubstrings(arr, n); return 0; } |
Java
// Java implementation to count of // palindromic Palindromic SubStrings// that can be formed from the arrayimport java.util.*;class GFG{ // Function to to check if possible// to make palindromic subStringstatic boolean isPossible(String A, String B) { B = sortString(B); for(int i = 0; i < (int)A.length(); i++) if(Arrays.binarySearch(B.toCharArray(), A.charAt(i)) > -1) return true; return false;} // Function to count of Palindromic SubStrings// that can be formed from the array.static int countPalindromicSubStrings(String s[], int n){ // Variable to store count int count = 0; // Traverse through all the pairs // in the array for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) if(isPossible(s[i], s[j])) count++; } return count;}static String sortString(String inputString) { // Convert input string to char array char tempArray[] = inputString.toCharArray(); // Sort tempArray Arrays.sort(tempArray); // Return new sorted string return new String(tempArray); } // Driver Code public static void main(String[] args) { String arr[] = { "gfg", "gfg" }; int n = 2; System.out.print(countPalindromicSubStrings(arr, n));} } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to count of # palindromic Palindromic Substrings# that can be formed from the array# Function to to check if possible# to make palindromic substringdef isPossible(A, B): B = sorted(B) c = 0 for i in range(len(A)): if A[i] in B: return True return False# Function to count of Palindromic # Substrings that can be formed # from the array.def countPalindromicSubstrings(s, n): # Variable to store count count = 0 # Traverse through all # Substrings in the array for i in range(n): for j in range(i + 1, n): if(isPossible(s[i], s[j])): count += 1 return count# Driver Code arr = ["gfg", "gfg"]n = 2print(countPalindromicSubstrings(arr, n))# This code is contributed by avanitrachhadiya2155 |
C#
// C# implementation to count of // palindromic Palindromic SubStrings// that can be formed from the arrayusing System;class GFG{ // Function to to check if possible// to make palindromic subStringstatic bool isPossible(String A, String B) { B = sortString(B); for(int i = 0; i < (int)A.Length; i++) if(Array.BinarySearch(B.ToCharArray(), A[i]) > -1) return true; return false;} // Function to count of Palindromic SubStrings// that can be formed from the array.static int countPalindromicSubStrings(String []s, int n){ // Variable to store count int count = 0; // Traverse through all the pairs // in the array for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) if(isPossible(s[i], s[j])) count++; } return count;}static String sortString(String inputString) { // Convert input string to char array char []tempArray = inputString.ToCharArray(); // Sort tempArray Array.Sort(tempArray); // Return new sorted string return new String(tempArray); } // Driver Code public static void Main(String[] args) { String []arr = { "gfg", "gfg" }; int n = 2; Console.Write(countPalindromicSubStrings(arr, n));} } // This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation// Function to to check if possible// to make palindromic substringfunction isPossible(A, B) { B = B.split('').sort().join(''); var c=0; for(var i = 0; i < A.length; i++) if(B.indexOf(A[i]) != -1) return true; return false;} // Function to count of Palindromic Substrings// that can be formed from the array.function countPalindromicSubstrings(s, n){ // variable to store count var count = 0; // Traverse through all the pairs // in the array for(var i = 0; i < n; i++){ for(var j = i + 1; j < n; j++) if(isPossible(s[i], s[j])) count++; } return count;}// Driver Code var arr = ["gfg", "gfg"]var n = 2document.write(countPalindromicSubstrings(arr, n)) // This code is contributed by shubhamsingh10</script> |
Output:
1
Time complexity: O(n2*mlogm) where m is length of string
Auxiliary Space: O(1)
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!
