Dada una string S y un entero K. La tarea es formar una string T tal que la string T sea un reordenamiento de la string S de manera que sea una K-String-Concatenada . Se dice que una string es una K-String-Concatenada si contiene exactamente K copias de alguna string.
Por ejemplo, la string «geekgeek» es una string concatenada de 2 strings formada al concatenar 2 copias de la string «geek».
Nota : Son posibles múltiples respuestas.
Ejemplos:
Entrada : s = “gkeekgee”, k=2
Salida : geekgeek
eegkeegk es otra posible K-Concatenated-String
Entrada : s = “abcd”, k=2
Salida : No es posible
Enfoque: para encontrar una ordenación válida que sea una string concatenada K, repita toda la string y mantenga una array de frecuencia para que los caracteres contengan la cantidad de veces que cada carácter aparece en una string. Dado que, en una string concatenada K, la cantidad de veces que aparece un carácter debe ser divisible por K. Si se encuentra algún carácter que no sigue a esto, entonces la string no se puede ordenar de ninguna manera para representar una string concatenada K, de lo contrario, puede haber exactamente (Frecuencia del i -ésimo carácter / K) copias del i -ésimo carácter en una sola copia de la k-string concatenada. Tales copias individuales cuando se repiten K veces forman una string concatenada K válida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to form a
// K-Concatenated-String from a given string
#include <bits/stdc++.h>
using namespace std;
// Function to print the k-concatenated string
string kStringGenerate(string str, int k)
{
// maintain a frequency table
// for lowercase letters
int frequency[26] = { 0 };
int len = str.length();
for (int i = 0; i < len; i++) {
// for each character increment its frequency
// in the frequency array
frequency[str[i] - 'a']++;
}
// stores a single copy of a string,
// which on repeating forms a k-string
string single_copy = "";
// iterate over frequency array
for (int i = 0; i < 26; i++) {
// if the character occurs in the string,
// check if it is divisible by k,
// if not divisible then k-string cant be formed
if (frequency[i] != 0) {
if ((frequency[i] % k) != 0) {
string ans = "Not Possible";
return ans;
}
else {
// ith character occurs (frequency[i]/k) times in a
// single copy of k-string
int total_occurrences = (frequency[i] / k);
for (int j = 0; j < total_occurrences; j++) {
single_copy += char(i + 97);
}
}
}
}
string kString;
// append the single copy formed k times
for (int i = 0; i < k; i++) {
kString += single_copy;
}
return kString;
}
// Driver Code
int main()
{
string str = "gkeekgee";
int K = 2;
string kString = kStringGenerate(str, K);
cout << kString;
return 0;
}
Java
// Java program to form a
// K-Concatenated-String
// from a given string
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG
{
// Function to print
// the k-concatenated string
static String kStringGenerate(String str,
int k)
{
// maintain a frequency table
// for lowercase letters
int frequency[] = new int[26];
Arrays.fill(frequency,0);
int len = str.length();
for (int i = 0; i < len; i++)
{
// for each character
// increment its frequency
// in the frequency array
frequency[str.charAt(i) - 'a']++;
}
// stores a single copy
// of a string, which on
// repeating forms a k-string
String single_copy = "";
// iterate over
// frequency array
for (int i = 0; i < 26; i++)
{
// if the character occurs
// in the string, check if
// it is divisible by k,
// if not divisible then
// k-string cant be formed
if (frequency[i] != 0)
{
if ((frequency[i] % k) != 0)
{
String ans = "Not Possible";
return ans;
}
else
{
// ith character occurs
// (frequency[i]/k) times in
// a single copy of k-string
int total_occurrences = (frequency[i] / k);
for (int j = 0;
j < total_occurrences; j++)
{
single_copy += (char)(i + 97);
}
}
}
}
String kString = "";
// append the single
// copy formed k times
for (int i = 0; i < k; i++)
{
kString += single_copy;
}
return kString;
}
// Driver Code
public static void main(String[] args)
{
String str = "gkeekgee";
int K = 2;
String kString = kStringGenerate(str, K);
System.out.print(kString);
}
}
Python3
# Python 3 program to form a
# K-Concatenated-String from a given string
# Function to print the k-concatenated string
def kStringGenerate(st, k):
# maintain a frequency table
# for lowercase letters
frequency = [0] * 26
length = len(st)
for i in range(length):
# for each character increment its frequency
# in the frequency array
frequency[ord(st[i]) - ord('a')] += 1
# stores a single copy of a string,
# which on repeating forms a k-string
single_copy = ""
# iterate over frequency array
for i in range(26):
# if the character occurs in the string,
# check if it is divisible by k,
# if not divisible then k-string cant be formed
if (frequency[i] != 0):
if ((frequency[i] % k) != 0):
ans = "Not Possible"
return ans
else:
# ith character occurs (frequency[i]/k) times in a
# single copy of k-string
total_occurrences = (frequency[i] // k)
for j in range(total_occurrences):
single_copy += chr(i + 97)
kString = ""
# append the single copy formed k times
for i in range(k):
kString += single_copy
return kString
# Driver Code
if __name__ == "__main__":
st = "gkeekgee"
K = 2
kString = kStringGenerate(st, K)
print(kString)
# This code is contributed by ukasp.
C#
// C# program to form a
// K-Concatenated-String
// from a given string
using System;
class GFG
{
// Function to print
// the k-concatenated string
static String kStringGenerate(String str,
int k)
{
// maintain a frequency table
// for lowercase letters
int []frequency = new int[26];
int len = str.Length;
for (int i = 0; i < len; i++)
{
// for each character
// increment its frequency
// in the frequency array
frequency[str[i]- 'a']++;
}
// stores a single copy
// of a string, which on
// repeating forms a k-string
String single_copy = "";
// iterate over
// frequency array
for (int i = 0; i < 26; i++)
{
// if the character occurs
// in the string, check if
// it is divisible by k,
// if not divisible then
// k-string cant be formed
if (frequency[i] != 0)
{
if ((frequency[i] % k) != 0)
{
String ans = "Not Possible";
return ans;
}
else
{
// ith character occurs
// (frequency[i]/k) times in
// a single copy of k-string
int total_occurrences = (frequency[i] / k);
for (int j = 0;
j < total_occurrences; j++)
{
single_copy += (char)(i + 97);
}
}
}
}
String kString = "";
// append the single
// copy formed k times
for (int i = 0; i < k; i++)
{
kString += single_copy;
}
return kString;
}
// Driver Code
public static void Main(String[] args)
{
String str = "gkeekgee";
int K = 2;
String kString = kStringGenerate(str, K);
Console.Write(kString);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to form a
// K-Concatenated-String
// from a given string
// Function to print
// the k-concatenated string
function kStringGenerate(str, k) {
// maintain a frequency table
// for lowercase letters
var frequency = new Array(26).fill(0);
var len = str.length;
for (var i = 0; i < len; i++) {
// for each character
// increment its frequency
// in the frequency array
frequency[str[i].charCodeAt(0) - "a".charCodeAt(0)]++;
}
// stores a single copy
// of a string, which on
// repeating forms a k-string
var single_copy = "";
// iterate over
// frequency array
for (var i = 0; i < 26; i++) {
// if the character occurs
// in the string, check if
// it is divisible by k,
// if not divisible then
// k-string cant be formed
if (frequency[i] != 0) {
if (frequency[i] % k != 0) {
var ans = "Not Possible";
return ans;
} else {
// ith character occurs
// (frequency[i]/k) times in
// a single copy of k-string
var total_occurrences = parseInt(frequency[i] / k);
for (var j = 0; j < total_occurrences; j++) {
single_copy += String.fromCharCode(i + 97);
}
}
}
}
var kString = "";
// append the single
// copy formed k times
for (var i = 0; i < k; i++) {
kString += single_copy;
}
return kString;
}
// Driver Code
var str = "gkeekgee";
var K = 2;
var kString = kStringGenerate(str, K);
document.write(kString);
</script>
Producción:
eegkeegk
Complejidad de tiempo: O(N), donde N es la longitud de la string.