Dada una array de strings arr[] , la tarea es contar el par de strings cuya concatenación de substrings forma un palíndromo.
Ejemplos:
Entrada: arr[] = {“gfg”, “gfg”}
Salida: 1
Explicación:
Una forma posible de elegir s1 y s2 es s1 = “gf”, s2 = “g” tal que s1 + s2 es decir, “gfg” es un palíndromo.
Entrada: arr[] = {“abc”, B = “def”}
Salida: 0
Enfoque : la observación clave en el problema es que si ambas strings tienen al menos un carácter común, digamos ‘c’, entonces podemos formar una string palindrómica. Por lo tanto, verifique para todos los pares en la array que haya un carácter común en la string o no.
A continuación se muestra la implementación del enfoque anterior:
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 substring
bool 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 array
import java.util.*;
class GFG{
// Function to to check if possible
// to make palindromic subString
static 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 substring def 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 = 2 print(countPalindromicSubstrings(arr, n)) # This code is contributed by avanitrachhadiya2155
C#
// C# implementation to count of
// palindromic Palindromic SubStrings
// that can be formed from the array
using System;
class GFG{
// Function to to check if possible
// to make palindromic subString
static 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 substring
function 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 = 2
document.write(countPalindromicSubstrings(arr, n))
// This code is contributed by shubhamsingh10
</script>
Producción:
1
Complejidad de tiempo: O(n 2 *mlogm) donde m es la longitud de la string
Espacio Auxiliar: O(1)