Dada una string str de longitud N y un entero K , la tarea es formar K strings diferentes eligiendo caracteres de la string dada de tal manera que todas las strings formadas sean palíndromos y la longitud de la string más pequeña entre las K strings sea la máxima posible. .
Ejemplos:
Entrada : str = “qrsprtps”, K = 2
Salida : 3
Explicación : Las 2 strings son: “pqp” y “rssr”.
Usando 2 ‘p’ y 1 ‘q’ se forma la 1ra cuerda y usando 2 ‘r’ y 2 ‘s’ se forma la 2da cuerda.
La primera cuerda es la más pequeña entre las K cuerdas y tiene una longitud de 3, por lo que la respuesta es 3.Entrada: str = “aaaabcbabca”, K = 3
Salida: 3
Explicación: Las posibles 3 strings palindrómicas de máxima longitud posible son: “aba”, “aba”, “aba”.
La longitud de la cuerda más pequeña entre estas es 3.
Enfoque: El enfoque se basa en la técnica Greedy . Intente distribuir un par de caracteres iguales a K strings por igual. Haga pares de caracteres idénticos para asegurarse de que la string formada sea un palíndromo. Un palíndromo de longitud par de longitud N tendrá N/2 de tales pares y uno de longitud impar tendrá un carácter adicional junto con los N/2 pares.
- Cuente la frecuencia de los caracteres en la string dada y el número de pares que se pueden formar con esos caracteres.
- Distribuya estos pares entre K strings siempre que haya K pares disponibles. (es decir, si hay 5 pares de este tipo y K = 2, entonces, distribuya 2 pares a cada uno para que se pueda formar una string palindrómica de 4 longitudes, un solo par se dejará sin distribuir)
- Ahora habrá todas las cuerdas palindrómicas de longitud uniforme . Como los pares que quedan no se pueden distribuir entre todas las strings, la string más pequeña tendrá una longitud del doble del número de pares de caracteres distribuidos en cada una de las strings.
- Intente agregar 1 carácter más para ver si se puede formar una string de longitud impar.
- De los caracteres restantes, es decir, los caracteres que no formaban parte de los pares y los caracteres del par sobrante, agregue 1 carácter a cada string para aumentar la longitud máxima en 1.
- Si hay al menos K de tales caracteres presentes, entonces solo la longitud mínima se puede aumentar en uno para todas las strings.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum possible
// minimum length among the
// K palindromic strings formed
// from given string str
int form_K_Strings(string& str, int k)
{
int n = str.size();
unordered_map<char, int> freq;
// Storing the frequency of the characters
for (auto i : str)
freq[i]++;
// Traversing the map to count
// the number of pairs
// that can be formed
// and count the remaining
// individual characters
int pairs = 0, remChar = 0;
for (auto i : freq) {
pairs += (i.second / 2);
if (i.second % 2 == 1)
remChar++;
}
// Calculating the number of pairs
// each string will receive
// upon equally distributing.
int distributed = pairs / k;
// Length of these strings will be
// twice of the pairs received.
// This is length of the smallest string
int res = distributed * 2;
// If some pairs are left then
// characters of the pairs can be treated
// as individual remaining characters and
// each pair will give 2 such characters
int remPairs = pairs % k;
remChar += 2 * remPairs;
// If atleast k remaining characters
// then we can add 1 character to
// each of the strings to form
// an odd length palindrome.
// So now the length of the smallest
// string will increase by 1.
if (remChar >= k)
res++;
return res;
}
// Driver code
int main()
{
string str = "qrsprtps";
int K = 2;
// Function call
cout << form_K_Strings(str, K);
return 0;
}
Java
// JAVA code to implement the approach
import java.util.*;
class GFG
{
// Function to find the maximum possible
// minimum length among the
// K palindromic strings formed
// from given string str
public static int form_K_Strings(String str, int k)
{
int n = str.length();
HashMap<Character, Integer> freq = new HashMap<>();
// Stroring the frequency of the characters
char[] strArray = str.toCharArray();
for (char c : strArray) {
if (freq.containsKey(c)) {
freq.put(c, freq.get(c) + 1);
}
else {
freq.put(c, 1);
}
}
// Traversing the map to count
// the number of pairs
// that can be formed
// and count the remaining
// individual characters
int pairs = 0, remChar = 0;
for (Map.Entry<Character, Integer> i :
freq.entrySet()) {
pairs += (i.getValue() / 2);
if (i.getValue() % 2 == 1)
remChar++;
}
// Calculating the number of pairs
// each string will receive
// upon equally distributing.
int distributed = pairs / k;
// Length of these strings will be
// twice of the pairs received.
// This is length of the smallest string
int res = distributed * 2;
// If some pairs are left then
// characters of the pairs can be treated
// as individual remaining characters and
// each pair will give 2 such characters
int remPairs = pairs % k;
remChar += 2 * remPairs;
// If atleast k remaining characters
// then we can add 1 character to
// each of the strings to form
// an odd length palindrome.
// So now the length of the smallest
// string will increase by 1.
if (remChar >= k)
res++;
return res;
}
// Driver code
public static void main(String[] args)
{
String str = "qrsprtps";
int K = 2;
// Function call
System.out.print(form_K_Strings(str, K));
}
}
// This code is contributed by Taranpreet
Python3
# Python 3 code to implement the approach from collections import defaultdict # Function to find the maximum possible # minimum length among the # K palindromic strings formed # from given string str def form_K_Strings(st, k): n = len(st) freq = defaultdict(int) # Storing the frequency of the characters for i in st: freq[i] += 1 # Traversing the map to count # the number of pairs # that can be formed # and count the remaining # individual characters pairs = 0 remChar = 0 for i in freq: pairs += (freq[i] // 2) if (freq[i] % 2 == 1): remChar += 1 # Calculating the number of pairs # each string will receive # upon equally distributing. distributed = pairs // k # Length of these strings will be # twice of the pairs received. # This is length of the smallest string res = distributed * 2 # If some pairs are left then # characters of the pairs can be treated # as individual remaining characters and # each pair will give 2 such characters remPairs = pairs % k remChar += 2 * remPairs # If atleast k remaining characters # then we can add 1 character to # each of the strings to form # an odd length palindrome. # So now the length of the smallest # string will increase by 1. if (remChar >= k): res += 1 return res # Driver code if __name__ == "__main__": st = "qrsprtps" K = 2 # Function call print(form_K_Strings(st, K)) # This code is contributed by ukasp.
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the maximum possible
// minimum length among the
// K palindromic strings formed
// from given string str
static int form_K_Strings(string str, int k)
{
int n = str.Length;
Dictionary<char, int> freq =
new Dictionary<char, int>();
// Stroring the frequency of the characters
char[] strArray = str.ToCharArray();
foreach (char c in strArray) {
if (!freq.ContainsKey(c)) {
freq.Add(c, 1);
}
else {
freq += 1;
}
}
// Traversing the map to count
// the number of pairs
// that can be formed
// and count the remaining
// individual characters
int pairs = 0, remChar = 0;
foreach(KeyValuePair<char, int> i in freq)
{
pairs += (i.Value / 2);
if (i.Value % 2 == 1)
remChar++;
}
// Calculating the number of pairs
// each string will receive
// upon equally distributing.
int distributed = pairs / k;
// Length of these strings will be
// twice of the pairs received.
// This is length of the smallest string
int res = distributed * 2;
// If some pairs are left then
// characters of the pairs can be treated
// as individual remaining characters and
// each pair will give 2 such characters
int remPairs = pairs % k;
remChar += 2 * remPairs;
// If atleast k remaining characters
// then we can add 1 character to
// each of the strings to form
// an odd length palindrome.
// So now the length of the smallest
// string will increase by 1.
if (remChar >= k)
res++;
return res;
}
// Driver code
public static void Main()
{
string str = "qrsprtps";
int K = 2;
// Function call
Console.Write(form_K_Strings(str, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the maximum possible
// minimum length among the
// K palindromic strings formed
// from given string str
function form_K_Strings(str, k)
{
let n = str.length;
let freq = new Map();
// Stroring the frequency of the characters
for (let i = 0; i < str.length; i++) {
if (freq.has(str[i])) {
freq.set(str[i], freq.get(str[i]) + 1)
}
else {
freq.set(str[i], 1)
}
}
// Traversing the map to count
// the number of pairs
// that can be formed
// and count the remaining
// individual characters
let pairs = 0, remChar = 0;
for (let [key, val] of freq) {
pairs += Math.floor(val / 2);
if (val % 2 == 1)
remChar++;
}
// Calculating the number of pairs
// each string will receive
// upon equally distributing.
let distributed = Math.floor(pairs / k);
// Length of these strings will be
// twice of the pairs received.
// This is length of the smallest string
let res = distributed * 2;
// If some pairs are left then
// characters of the pairs can be treated
// as individual remaining characters and
// each pair will give 2 such characters
let remPairs = pairs % k;
remChar += 2 * remPairs;
// If atleast k remaining characters
// then we can add 1 character to
// each of the strings to form
// an odd length palindrome.
// So now the length of the smallest
// string will increase by 1.
if (remChar >= k)
res++;
return res;
}
// Driver code
let str = "qrsprtps";
let K = 2;
// Function call
document.write(form_K_Strings(str, K));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)