Dada una string S , la tarea es dividir los caracteres de S para formar el número mínimo de strings palindrómicas .
Nota: Puede haber varias respuestas correctas.
Ejemplos:
Entrada: S = «geeksforgeeks»
Salida: {eegksrskgee, o, f}Explicación:
Debe haber al menos 3 strings «eegksrskgee», «o», «f». Las 3 cuerdas formadas son palíndromos.Entrada : S = “abbaa”
Salida: {“ababa”}Explicación:
La string dada S = “ababa” ya es una string palíndromo, por lo que solo se formará 1 string.Entrada: S = “abc”
Salida: {“a”, “b”, “c”}Explicación:
Debe haber al menos 3 strings «a», «b», «c». Las 3 cuerdas formadas son palíndromos.
Acercarse:
La observación principal es que una cuerda de palíndromo permanece igual si se invierte. La longitud de las cuerdas formadas no importa, así que trate de hacer una cuerda lo más grande posible. Si algún carácter no puede ser parte de una string palindrómica, inserte este carácter en una nueva string.
- El enfoque general sería almacenar la frecuencia de cada carácter y si para algún carácter la frecuencia es impar, entonces tenemos que crear una nueva string e incrementar nuestra respuesta en 1.
- Tenga en cuenta que si no hay caracteres con frecuencia impar, aún se necesita al menos una string, por lo que la respuesta final será max(1, caracteres de frecuencia impar).
- Para imprimir la string, almacene caracteres impares, caracteres de frecuencia en un vector y caracteres pares en otro vector.
- Forme una string palindrómica con strings que tengan caracteres impares y agregue una string con un número par de caracteres y todas las demás strings serán de un solo carácter.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return
// minimum palindromic strings formed
int minimumPalindromicStrings(string S)
{
// Store the length of string
int N = S.length();
// Iterate over the string
// and store the frequency of
// all characters A vector
// to store the frequency
vector<int> freq(26);
for (int i = 0; i < N; i++) {
freq[S[i] - 'a']++;
}
// Store the odd frequency characters
vector<int> oddFreqCharacters;
// Store the even frequency of characters
// in the same vector by dividing
// current frequency by 2 as one element
// will be used on left as well as right side
// Iterate through all possible characters
// and check the parity of frequency
for (int i = 0; i < 26; i++) {
if (freq[i] & 1) {
oddFreqCharacters.push_back(i);
freq[i]--;
}
freq[i] /= 2;
}
// store answer in a vector
vector<string> ans;
// if there are no odd Frequency characters
// then print the string with even characters
if (oddFreqCharacters.empty()) {
// store the left part
// of the palindromic string
string left = "";
for (int i = 0; i < 26; i++) {
for (int j = 0; j < freq[i]; j++) {
left += char(i + 'a');
}
}
string right = left;
// reverse the right part of the string
reverse(right.begin(), right.end());
// store the string in ans vector
ans.push_back(left + right);
}
else {
// take any character
// from off frequency element
string middle = "";
int c = oddFreqCharacters.back();
oddFreqCharacters.pop_back();
middle += char(c + 'a');
// repeat the above step to form
// left and right strings
string left = "";
for (int i = 0; i < 26; i++) {
for (int j = 0; j < freq[i]; j++) {
left += char(i + 'a');
}
}
string right = left;
// reverse the right part of the string
reverse(right.begin(), right.end());
// store the string in ans vector
ans.push_back(left + middle + right);
// store all other odd frequency strings
while (!oddFreqCharacters.empty()) {
int c = oddFreqCharacters.back();
oddFreqCharacters.pop_back();
string middle = "";
middle += char(c + 'a');
ans.push_back(middle);
}
}
// Print the answer
cout << "[";
for (int i = 0; i < ans.size(); i++) {
cout << ans[i];
if (i != ans.size() - 1) {
cout << ", ";
}
}
cout << "]";
return 0;
}
// Driver Code
int main()
{
string S = "geeksforgeeks";
minimumPalindromicStrings(S);
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to return
// minimum palindromic Strings formed
static int minimumPalindromicStrings(String S)
{
// Store the length of String
int N = S.length();
// Iterate over the String
// and store the frequency of
// all characters A vector
// to store the frequency
int[] freq = new int[26];
for (int i = 0; i < N; i++) {
freq[S.charAt(i) - 'a']++;
}
// Store the odd frequency characters
Vector<Integer> oddFreqCharacters = new Vector<Integer>();
// Store the even frequency of characters
// in the same vector by dividing
// current frequency by 2 as one element
// will be used on left as well as right side
// Iterate through all possible characters
// and check the parity of frequency
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 == 1) {
oddFreqCharacters.add(i);
freq[i]--;
}
freq[i] /= 2;
}
// store answer in a vector
Vector<String> ans = new Vector<String>();
// if there are no odd Frequency characters
// then print the String with even characters
if (oddFreqCharacters.isEmpty()) {
// store the left part
// of the palindromic String
String left = "";
for (int i = 0; i < 26; i++) {
for (int j = 0; j < freq[i]; j++) {
left += (char)(i + 'a');
}
}
String right = left;
// reverse the right part of the String
right = reverse(right);
// store the String in ans vector
ans.add(left + right);
}
else {
// take any character
// from off frequency element
String middle = "";
int c = oddFreqCharacters.lastElement();
oddFreqCharacters.remove(oddFreqCharacters.size()-1);
middle += (char)(c + 'a');
// repeat the above step to form
// left and right Strings
String left = "";
for (int i = 0; i < 26; i++) {
for (int j = 0; j < freq[i]; j++) {
left += (char)(i + 'a');
}
}
String right = left;
// reverse the right part of the String
right = reverse(right);
// store the String in ans vector
ans.add(left + middle + right);
// store all other odd frequency Strings
while (!oddFreqCharacters.isEmpty()) {
c = oddFreqCharacters.lastElement();
oddFreqCharacters.remove(oddFreqCharacters.size()-1);
middle = "";
middle += (char)(c + 'a');
ans.add(middle);
}
}
// Print the answer
System.out.print("[");
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i));
if (i != ans.size() - 1) {
System.out.print(", ");
}
}
System.out.print("]");
return 0;
}
static String reverse(String input) {
char[] a = input.toCharArray();
int l, r = a.length - 1;
for (l = 0; l < r; l++, r--) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.valueOf(a);
}
// Driver Code
public static void main(String[] args)
{
String S = "geeksforgeeks";
minimumPalindromicStrings(S);
}
}
// This code is contributed by 29AjayKumar
C#
// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to return
// minimum palindromic Strings formed
static int minimumPalindromicStrings(String S)
{
// Store the length of String
int N = S.Length;
// Iterate over the String
// and store the frequency of
// all characters A vector
// to store the frequency
int[] freq = new int[26];
for (int i = 0; i < N; i++) {
freq[S[i] - 'a']++;
}
// Store the odd frequency characters
List<int> oddFreqchars = new List<int>();
// Store the even frequency of characters
// in the same vector by dividing
// current frequency by 2 as one element
// will be used on left as well as right side
// Iterate through all possible characters
// and check the parity of frequency
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 == 1) {
oddFreqchars.Add(i);
freq[i]--;
}
freq[i] /= 2;
}
// store answer in a vector
List<String> ans = new List<String>();
// if there are no odd Frequency characters
// then print the String with even characters
if (oddFreqchars.Count==0) {
// store the left part
// of the palindromic String
String left = "";
for (int i = 0; i < 26; i++) {
for (int j = 0; j < freq[i]; j++) {
left += (char)(i + 'a');
}
}
String right = left;
// reverse the right part of the String
right = reverse(right);
// store the String in ans vector
ans.Add(left + right);
}
else {
// take any character
// from off frequency element
String middle = "";
int c = oddFreqchars[oddFreqchars.Count-1];
oddFreqchars.RemoveAt(oddFreqchars.Count-1);
middle += (char)(c + 'a');
// repeat the above step to form
// left and right Strings
String left = "";
for (int i = 0; i < 26; i++) {
for (int j = 0; j < freq[i]; j++) {
left += (char)(i + 'a');
}
}
String right = left;
// reverse the right part of the String
right = reverse(right);
// store the String in ans vector
ans.Add(left + middle + right);
// store all other odd frequency Strings
while (oddFreqchars.Count!=0) {
c = oddFreqchars[oddFreqchars.Count-1];
oddFreqchars.RemoveAt(oddFreqchars.Count-1);
middle = "";
middle += (char)(c + 'a');
ans.Add(middle);
}
}
// Print the answer
Console.Write("[");
for (int i = 0; i < ans.Count; i++) {
Console.Write(ans[i]);
if (i != ans.Count - 1) {
Console.Write(", ");
}
}
Console.Write("]");
return 0;
}
static String reverse(String input) {
char[] a = input.ToCharArray();
int l, r = a.Length - 1;
for (l = 0; l < r; l++, r--) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.Join("",a);
}
// Driver Code
public static void Main(String[] args)
{
String S = "geeksforgeeks";
minimumPalindromicStrings(S);
}
}
// This code is contributed by 29AjayKumar
Producción:
[eegksrskgee, o, f]
Complejidad de tiempo: O (N * 26)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA