Dadas dos strings S y P , la tarea es encontrar la string palíndromo más grande posible eligiendo caracteres de las strings S y P dadas después de reorganizar los caracteres.
Nota: Si hay muchas respuestas posibles, encuentre la T lexicográficamente más pequeña con la longitud máxima.
Ejemplos:
Entrada: S = “abad”, T = “eeff”
Salida: aefbfea
Explicación:
De la primera string “aba” y de la segunda string “effe” son palíndromos.
Use estos dos para hacer un nuevo palíndromo T “aefbfea” que es lexicográficamente más pequeño.
También T es de la máxima longitud posible.
Nota: “ada”, aunque esto dará T de la misma longitud, es decir, 7 pero eso no será lexicográficamente más pequeño.Entrada: S = “aeabb”, T = “dfedf”
Salida: abdeffedba
Explicación:
De la primera string “abeba” y de la segunda string “dfefd”, son palíndromos. Combine los dos para obtener T: «abdeffedba» es lexicográficamente más pequeño.
Enfoque: La idea es tomar todos los caracteres de las strings S y P que están presentes varias veces respectivamente. Como substrings, A y B de ambas strings tienen todos los caracteres que están presentes un número par de veces en S y P respectivamente para convertirse en el palíndromo más grande de la string principal. A continuación se muestran los pasos:
- Tome un solo carácter de las strings S y P , de modo que estén presentes en la mitad de los palíndromos tomados de cada string, respectivamente. Coloque ese elemento único en medio de T .
- Los casos posibles para tomar un elemento único de la substring A y B son:
- Si un elemento único está presente tanto en A como en B , tome ambos porque aumentará la longitud de T en 2 .
- Si los elementos únicos están presentes tanto en S como en P pero no en el mismo elemento, entonces tome el que es pequeño porque eso hará lexicográficamente el palíndromo T más pequeño .
- Si ningún elemento único está presente en ambos, haga la string T solo con elementos de A y B.
- Utilice el mapa desordenado para contar los caracteres que aparecen un número par de veces en la string principal. Además, use otro mapa para contar los caracteres que se usarán para hacer T .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find largest palindrome
// possible from S and P after rearranging
// characters to make palindromic string T
string mergePalindromes(string S, string P)
{
// Using unordered_map to store
// frequency of elements
// mapT will have freq of elements of T
unordered_map<char, int> mapS, mapP, mapT;
// Size of both the strings
int n = S.size(), m = P.size();
for (int i = 0; i < n; i++) {
mapS[S[i]]++;
}
for (int i = 0; i < m; i++) {
mapP[P[i]]++;
}
// Take all character in mapT which
// occur even number of times in
// respective strings & simultaneously
// update number of characters left in map
for (char i = 'a'; i <= 'z'; i++) {
if (mapS[i] % 2 == 0) {
mapT[i] += mapS[i];
mapS[i] = 0;
}
else {
mapT[i] += mapS[i] - 1;
mapS[i] = 1;
}
if (mapP[i] % 2 == 0) {
mapT[i] += mapP[i];
mapP[i] = 0;
}
else {
mapT[i] += mapP[i] - 1;
mapP[i] = 1;
}
}
// Check if a unique character is
// present in both string S and P
int check = 0;
for (char i = 'a'; i <= 'z'; i++) {
if (mapS[i] > 0 && mapP[i] > 0) {
mapT[i] += 2;
check = 1;
break;
}
}
// Making string T in two halves
// half1 - first half
// half2 - second half
string half1 = "", half2 = "";
for (char i = 'a'; i <= 'z'; i++) {
for (int j = 0; (2 * j) < mapT[i]; j++) {
half1 += i;
half2 += i;
}
}
// Reverse the half2 to attach with half1
// to make palindrome T
reverse(half2.begin(), half2.end());
// If same unique element is present
// in both S and P, then taking that only
// which is already taken through mapT
if (check) {
return half1 + half2;
}
// If same unique element is not
// present in S and P, then take
// characters that make string T
// lexicographically smallest
for (char i = 'a'; i <= 'z'; i++) {
if (mapS[i] > 0 || mapP[i] > 0) {
half1 += i;
return half1 + half2;
}
}
// If no unique element is
// present in both string S and P
return half1 + half2;
}
// Driver Code
int main()
{
// Given two strings S and P
string S = "aeabb";
string P = "dfedf";
// Function Call
cout << mergePalindromes(S, P);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to find largest palindrome
// possible from S and P after rearranging
// characters to make palindromic string T
static String mergePalindromes(StringBuilder S,
StringBuilder P)
{
// Using unordered_map to store
// frequency of elements
// mapT will have freq of elements of T
Map<Character, Integer> mapS = new HashMap<>(),
mapP = new HashMap<>(),
mapT = new HashMap<>();
// Size of both the strings
int n = S.length(), m = P.length();
for(int i = 0; i < n; i++)
{
mapS.put(S.charAt(i),
mapS.getOrDefault(S.charAt(i), 0) + 1);
}
for(int i = 0; i < m; i++)
{
mapP.put(P.charAt(i),
mapP.getOrDefault(P.charAt(i), 0) + 1);
}
// Take all character in mapT which
// occur even number of times in
// respective strings & simultaneously
// update number of characters left in map
for(char i = 'a'; i <= 'z'; i++)
{
if (mapS.getOrDefault(i, 0) % 2 == 0)
{
mapT.put(i,mapT.getOrDefault(i, 0) +
mapS.getOrDefault(i, 0));
mapS.put(i, 0);
}
else
{
mapT.put(i,mapT.getOrDefault(i, 0) +
mapS.getOrDefault(i, 0) - 1);
mapS.put(i, 1);
}
if (mapP.getOrDefault(i, 0) % 2 == 0)
{
mapT.put(i, mapT.getOrDefault(i, 0) +
mapP.getOrDefault(i, 0));
mapP.put(i, 0);
}
else
{
mapT.put(i, mapT.getOrDefault(i, 0) +
mapP.getOrDefault(i, 0) - 1);
mapP.put(i, 1);
}
}
// Check if a unique character is
// present in both string S and P
int check = 0;
for(char i = 'a'; i <= 'z'; i++)
{
if (mapS.getOrDefault(i, 0) > 0 &&
mapP.getOrDefault(i, 0) > 0)
{
mapT.put(i, mapT.getOrDefault(i, 0) + 2);
check = 1;
break;
}
}
// Making string T in two halves
// half1 - first half
// half2 - second half
StringBuilder half1 = new StringBuilder(),
half2 = new StringBuilder();
for(char i = 'a'; i <= 'z'; i++)
{
for(int j = 0;
(2 * j) < mapT.getOrDefault(i, 0);
j++)
{
half1.append(i);
half2.append(i);
}
}
// Reverse the half2 to attach with half1
// to make palindrome T
StringBuilder tmp = half2.reverse();
// If same unique element is present
// in both S and P, then taking that only
// which is already taken through mapT
if (check == 1)
{
return half1.append(tmp).toString();
}
// If same unique element is not
// present in S and P, then take
// characters that make string T
// lexicographically smallest
for(char i = 'a'; i <= 'z'; i++)
{
if (mapS.getOrDefault(i, 0) > 0 ||
mapP.getOrDefault(i, 0) > 0)
{
half1.append(i);
return half1.append(tmp).toString();
}
}
// If no unique element is
// present in both string S and P
return half1.append(tmp).toString();
}
// Driver code
public static void main (String[] args)
{
// Given two strings S and P
StringBuilder S = new StringBuilder("aeabb");
StringBuilder P = new StringBuilder("dfedf");
// Function call
System.out.println(mergePalindromes(S, P));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
from collections import defaultdict
# Function to find largest palindrome
# possible from S and P after rearranging
# characters to make palindromic string T
def mergePalindromes(S, P):
# Using unordered_map to store
# frequency of elements
# mapT will have freq of elements of T
mapS = defaultdict(lambda : 0)
mapP = defaultdict(lambda : 0)
mapT = defaultdict(lambda : 0)
# Size of both the strings
n = len(S)
m = len(P)
for i in range(n):
mapS[ord(S[i])] += 1
for i in range(m):
mapP[ord(P[i])] += 1
# Take all character in mapT which
# occur even number of times in
# respective strings & simultaneously
# update number of characters left in map
for i in range(ord('a'), ord('z') + 1):
if(mapS[i] % 2 == 0):
mapT[i] += mapS[i]
mapS[i] = 0
else:
mapT[i] += mapS[i] - 1
mapS[i] = 1
if (mapP[i] % 2 == 0):
mapT[i] += mapP[i]
mapP[i] = 0
else:
mapT[i] += mapP[i] - 1
mapP[i] = 1
# Check if a unique character is
# present in both string S and P
check = 0
for i in range(ord('a'), ord('z') + 1):
if (mapS[i] > 0 and mapP[i] > 0):
mapT[i] += 2
check = 1
break
# Making string T in two halves
# half1 - first half
# half2 - second half
half1, half2 = "", ""
for i in range(ord('a'), ord('z') + 1):
j = 0
while((2 * j) < mapT[i]):
half1 += chr(i)
half2 += chr(i)
j += 1
# Reverse the half2 to attach with half1
# to make palindrome
half2 = half2[::-1]
# If same unique element is present
# in both S and P, then taking that only
# which is already taken through mapT
if(check):
return half1 + half2
# If same unique element is not
# present in S and P, then take
# characters that make string T
# lexicographically smallest
for i in range(ord('a'), ord('z') + 1):
if(mapS[i] > 0 or mapP[i] > 0):
half1 += chr(i)
return half1 + half2
# If no unique element is
# present in both string S and P
return half1 + half2
# Driver Code
# Given string S and P
S = "aeabb"
P = "dfedf"
# Function call
print(mergePalindromes(S, P))
# This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Text;
class GFG{
// Function to find largest palindrome
// possible from S and P after rearranging
// characters to make palindromic string T
static string mergePalindromes(string S,
string P)
{
// Using unordered_map to store
// frequency of elements mapT will
// have freq of elements of T
Dictionary<char,
int> mapS = new Dictionary<char,
int>();
Dictionary<char,
int> mapP = new Dictionary<char,
int>();
Dictionary<char,
int> mapT = new Dictionary<char,
int>();
// Size of both the strings
int n = S.Length, m = P.Length;
for(char i = 'a'; i <= 'z'; i++)
{
mapS[i] = 0;
mapP[i] = 0;
mapT[i] = 0;
}
for(int i = 0; i < n; i++)
{
mapS[S[i]]++;
}
for(int i = 0; i < m; i++)
{
mapP[P[i]]++;
}
// Take all character in mapT which
// occur even number of times in
// respective strings & simultaneously
// update number of characters left in map
for(char i = 'a'; i <= 'z'; i++)
{
if (mapS[i] % 2 == 0)
{
mapT[i] += mapS[i];
mapS[i] = 0;
}
else
{
mapT[i] += mapS[i] - 1;
mapS[i] = 1;
}
if (mapP[i] % 2 == 0)
{
mapT[i] += mapP[i];
mapP[i] = 0;
}
else
{
mapT[i] += mapP[i] - 1;
mapP[i] = 1;
}
}
// Check if a unique character is
// present in both string S and P
int check = 0;
for(char i = 'a'; i <= 'z'; i++)
{
if (mapS[i] > 0 && mapP[i] > 0)
{
mapT[i] += 2;
check = 1;
break;
}
}
// Making string T in two halves
// half1 - first half
// half2 - second half
string half1 = "", half2 = "";
for(char i = 'a'; i <= 'z'; i++)
{
for(int j = 0; (2 * j) < mapT[i]; j++)
{
half1 += i;
half2 += i;
}
}
// Reverse the half2 to attach with half1
// to make palindrome T
char[] tmp = half2.ToCharArray();
Array.Reverse(tmp);
half2 = new string(tmp);
// If same unique element is present
// in both S and P, then taking that only
// which is already taken through mapT
if (check != 0)
{
return half1 + half2;
}
// If same unique element is not
// present in S and P, then take
// characters that make string T
// lexicographically smallest
for(char i = 'a'; i <= 'z'; i++)
{
if (mapS[i] > 0 || mapP[i] > 0)
{
half1 += i;
return half1 + half2;
}
}
// If no unique element is
// present in both string S and P
return half1 + half2;
}
// Driver Code
public static void Main(string []args)
{
// Given two strings S and P
string S = "aeabb";
string P = "dfedf";
Console.Write(mergePalindromes(S, P));
}
}
// This code is contributed by rutvik_56
Producción:
abdeffedba
Complejidad de tiempo: O(N), donde N es la longitud de la string S o P.
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pradyumanagarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA