Dada una string S que consta de N caracteres y un entero positivo K , la tarea es encontrar el número mínimo de operaciones requeridas para generar la string S a partir de una string temporal aleatoria de tamaño K e insertar la subsecuencia de cualquier longitud fija de la string aleatoria en la string aleatoria. Si es imposible generar la string S , imprima «-1» .
Ejemplos:
Entrada: S = «toffee», N = 4
Salida: 2 tofe
Explicación:
Considere la string temporal aleatoria como «tofe» que tiene una longitud K(= 4) y realice los siguientes pasos:
Operación 1: Tome una subsecuencia de longitud 1 de la string temporal como ‘f’ y después de insertar la subsecuencia en la string «tofe» modifica la string a «toffe».
Operación 2: Tome una subsecuencia de longitud 1 de la string temporal como ‘e’ y después de insertar la subsecuencia en la string «toffe» modifica la string a «toffee».Por lo tanto, el número mínimo de operaciones requeridas es 2.
Entrada: S = “libro”, N = 2
Salida: -1
Enfoque: este problema se puede resolver utilizando el enfoque codicioso y la búsqueda binaria . Siga los pasos a continuación para resolver este problema:
- Inicialice una array , digamos las cantidades[] que almacena la frecuencia de cada carácter de la string S.
- Itere en el rango [0, N – 1] usando la variable i e incremente la frecuencia del carácter actual en 1 en la array cantidades[] .
- Encuentre contar caracteres únicos en la string S y almacenarlos en una variable, por ejemplo, contar .
- Si el recuento es mayor que N, devuelva -1 .
- Ahora, realice la búsqueda binaria para encontrar la string resultante y realice los siguientes pasos:
- Inicialice dos variables altas como 10 5 y bajas como 0 .
- Iterar hasta que el valor de (alto – bajo) sea mayor que 1 y realizar los siguientes pasos:
- Actualice el valor de total como 0 y mid como (alto + bajo) / 2 .
- Iterar en el rango [0, 25] usando la variable i y si el valor de las cantidades [i] es mayor que 0 , entonces incremente el total en (cantidades [i] – 1)/mid + 1 .
- Si el total es menor que igual a N , actualice el valor de alto como medio . De lo contrario, actualice el valor de low como mid .
- Después de completar los pasos anteriores, imprima el valor de alto e itere en el rango [0, 25] e imprima la string resultante.
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 the minimum number
// of string required to generate
// the original string
void findString(string S, int N)
{
// Stores the frequency of each
// character of String S
int amounts[26];
// Iterate over the range [0, 25]
for (int i = 0; i < 26; i++) {
amounts[i] = 0;
}
// Stores the frequency of each
// character of String S
for (int i = 0; i < S.length(); i++) {
amounts[int(S[i]) - 97]++;
}
int count = 0;
// Count unique characters in S
for (int i = 0; i < 26; i++) {
if (amounts[i] > 0)
count++;
}
// If unique characters is greater
// then N, then return -1
if (count > N) {
cout << "-1";
}
// Otherwise
else {
string ans = "";
int high = 100001;
int low = 0;
int mid, total;
// Perform Binary Search
while ((high - low) > 1) {
total = 0;
// Find the value of mid
mid = (high + low) / 2;
// Iterate over the range
// [0, 26]
for (int i = 0; i < 26; i++) {
// If the amount[i] is
// greater than 0
if (amounts[i] > 0) {
total += (amounts[i] - 1)
/ mid
+ 1;
}
}
// Update the ranges
if (total <= N) {
high = mid;
}
else {
low = mid;
}
}
cout << high << " ";
total = 0;
// Find the resultant string
for (int i = 0; i < 26; i++) {
if (amounts[i] > 0) {
total += (amounts[i] - 1)
/ high
+ 1;
for (int j = 0;
j < ((amounts[i] - 1)
/ high
+ 1);
j++) {
// Generate the subsequence
ans += char(i + 97);
}
}
}
// If the length of resultant
// string is less than N than
// add a character 'a'
for (int i = total; i < N; i++) {
ans += 'a';
}
reverse(ans.begin(), ans.end());
// Print the string
cout << ans;
}
}
// Driver Code
int main()
{
string S = "toffee";
int K = 4;
findString(S, K);
return 0;
}
Java
// Java code for above approach
import java.util.*;
class GFG{
// Function to find the minimum number
// of string required to generate
// the original string
static void findString(String S, int N)
{
// Stores the frequency of each
// character of string S
int[] amounts = new int[26];
// Iterate over the range [0, 25]
for (int i = 0; i < 26; i++) {
amounts[i] = 0;
}
// Stores the frequency of each
// character of string S
for (int i = 0; i < S.length(); i++) {
amounts[(int)(S.charAt(i) - 97)]++;
}
int count = 0;
// Count unique characters in S
for (int i = 0; i < 26; i++) {
if (amounts[i] > 0)
count++;
}
// If unique characters is greater
// then N, then return -1
if (count > N) {
System.out.print("-1");
}
// Otherwise
else {
String ans = "";
int high = 100001;
int low = 0;
int mid, total;
// Perform Binary Search
while ((high - low) > 1) {
total = 0;
// Find the value of mid
mid = (high + low) / 2;
// Iterate over the range
// [0, 26]
for (int i = 0; i < 26; i++) {
// If the amount[i] is
// greater than 0
if (amounts[i] > 0) {
total += (amounts[i] - 1)
/ mid
+ 1;
}
}
// Update the ranges
if (total <= N) {
high = mid;
}
else {
low = mid;
}
}
System.out.print(high + " ");
total = 0;
// Find the resultant string
for (int i = 0; i < 26; i++) {
if (amounts[i] > 0) {
total += (amounts[i] - 1)
/ high
+ 1;
for (int j = 0;
j < ((amounts[i] - 1)
/ high
+ 1);
j++) {
// Generate the subsequence
ans += (char)(i + 97);
}
}
}
// If the length of resultant
// string is less than N than
// add a character 'a'
for (int i = total; i < N; i++) {
ans += 'a';
}
String reverse = "";
int Len = ans.length() - 1;
while(Len >= 0)
{
reverse = reverse + ans.charAt(Len);
Len--;
}
// Print the string
System.out.print(reverse);
}
}
// Driver Code
public static void main(String[] args)
{
String S = "toffee";
int K = 4;
findString(S, K);
}
}
// This code is contributed by target_2.
Python3
# Python3 program for the above approach
# Function to find the minimum number
# of string required to generate
# the original string
def findString(S, N):
# Stores the frequency of each
# character of String S
amounts = [0] * 26
# Stores the frequency of each
# character of String S
for i in range(len(S)):
amounts[ord(S[i]) - 97] += 1
count = 0
# Count unique characters in S
for i in range(26):
if amounts[i] > 0:
count += 1
# If unique characters is greater
# then N, then return -1
if count > N:
print("-1")
# Otherwise
else:
ans = ""
high = 100001
low = 0
# Perform Binary Search
while (high - low) > 1:
total = 0
# Find the value of mid
mid = (high + low) // 2
# Iterate over the range
# [0, 26]
for i in range(26):
# If the amount[i] is
# greater than 0
if amounts[i] > 0:
total += (amounts[i] - 1) // mid + 1
# Update the ranges
if total <= N:
high = mid
else:
low = mid
print(high, end = " ")
total = 0
# Find the resultant string
for i in range(26):
if amounts[i] > 0:
total += (amounts[i] - 1) // high + 1
for j in range((amounts[i] - 1) // high + 1):
ans += chr(i + 97)
# If the length of resultant
# string is less than N than
# add a character 'a'
for i in range(total, N):
ans += 'a'
ans = ans[::-1]
# Print the string
print(ans)
# Driver code
S = "toffee"
K = 4
findString(S, K)
# This code is contributed by Parth Manchanda
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum number
// of string required to generate
// the original string
static void findString(string S, int N)
{
// Stores the frequency of each
// character of string S
int[] amounts = new int[26];
// Iterate over the range [0, 25]
for (int i = 0; i < 26; i++) {
amounts[i] = 0;
}
// Stores the frequency of each
// character of string S
for (int i = 0; i < S.Length; i++) {
amounts[(int)(S[i] - 97)]++;
}
int count = 0;
// Count unique characters in S
for (int i = 0; i < 26; i++) {
if (amounts[i] > 0)
count++;
}
// If unique characters is greater
// then N, then return -1
if (count > N) {
Console.Write("-1");
}
// Otherwise
else {
string ans = "";
int high = 100001;
int low = 0;
int mid, total;
// Perform Binary Search
while ((high - low) > 1) {
total = 0;
// Find the value of mid
mid = (high + low) / 2;
// Iterate over the range
// [0, 26]
for (int i = 0; i < 26; i++) {
// If the amount[i] is
// greater than 0
if (amounts[i] > 0) {
total += (amounts[i] - 1)
/ mid
+ 1;
}
}
// Update the ranges
if (total <= N) {
high = mid;
}
else {
low = mid;
}
}
Console.Write(high + " ");
total = 0;
// Find the resultant string
for (int i = 0; i < 26; i++) {
if (amounts[i] > 0) {
total += (amounts[i] - 1)
/ high
+ 1;
for (int j = 0;
j < ((amounts[i] - 1)
/ high
+ 1);
j++) {
// Generate the subsequence
ans += (char)(i + 97);
}
}
}
// If the length of resultant
// string is less than N than
// add a character 'a'
for (int i = total; i < N; i++) {
ans += 'a';
}
string reverse = "";
int Len = ans.Length - 1;
while(Len >= 0)
{
reverse = reverse + ans[Len];
Len--;
}
// Print the string
Console.Write(reverse);
}
}
// Driver Code
public static void Main()
{
string S = "toffee";
int K = 4;
findString(S, K);
}
}
// This code is contributed by splevel62.
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of string required to generate
// the original string
function findString(S, N)
{
// Stores the frequency of each
// character of String S
let amounts = new Array(26);
// Iterate over the range [0, 25]
for (let i = 0; i < 26; i++) {
amounts[i] = 0;
}
// Stores the frequency of each
// character of String S
for (let i = 0; i < S.length; i++) {
amounts[S[i].charCodeAt(0) - 97]++;
}
let count = 0;
// Count unique characters in S
for (let i = 0; i < 26; i++) {
if (amounts[i] > 0) count++;
}
// If unique characters is greater
// then N, then return -1
if (count > N) {
document.write("-1");
}
// Otherwise
else {
let ans = "";
let high = 100001;
let low = 0;
let mid, total;
// Perform Binary Search
while (high - low > 1) {
total = 0;
// Find the value of mid
mid = Math.floor((high + low) / 2);
// Iterate over the range
// [0, 26]
for (let i = 0; i < 26; i++) {
// If the amount[i] is
// greater than 0
if (amounts[i] > 0) {
total += Math.floor((amounts[i] - 1) / mid + 1);
}
}
// Update the ranges
if (total <= N) {
high = mid;
} else {
low = mid;
}
}
document.write(high + " ");
total = 0;
// Find the resultant string
for (let i = 0; i < 26; i++) {
if (amounts[i] > 0) {
total += Math.floor((amounts[i] - 1) / high + 1);
for (let j = 0; j < Math.floor((amounts[i] - 1) / high + 1); j++) {
// Generate the subsequence
ans += String.fromCharCode(i + 97);
}
}
}
// If the length of resultant
// string is less than N than
// add a character 'a'
for (let i = total; i < N; i++) {
ans += "a";
}
ans = ans.split("").reverse().join("");
// Print the string
document.write(ans);
}
}
// Driver Code
let S = "toffee";
let K = 4;
findString(S, K);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
2 tofe
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por samarpitsmarty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA