Dadas dos strings A y B , la tarea es encontrar lexicográficamente la permutación más pequeña de la string B tal que contenga cada substring de la string A como su substring . Escriba “ -1” si no es posible un arreglo válido.
Ejemplos:
Entrada: A = “aa”, B = “ababab”
Salida: aaabbb
Explicación:
Todas las substrings posibles de A son (‘a’, ‘a’, ‘aa’)
Reorganice la string B a “aaabb”.
Ahora “aaabb” es lexicográficamente el arreglo más pequeño de B que contiene todas las substrings de A.Entrada: A = “aaa”, B = “ramialsadaka”
Salida: aaaaadiklmrs
Explicación:
Todas las substrings posibles de A son (‘a’, ‘aa’, ‘aaa’)
Reorganice la string B a “aaaaadiklmrs”.
Ahora “aaaaadiklmrs” es la disposición lexicográficamente más pequeña de B que contiene todas las substrings de A.
Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones posibles de la string B y luego, a partir de todas estas permutaciones, encontrar lexicográficamente la permutación más pequeña que contiene todas las substrings de A.
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la observación principal es que la string más pequeña que contiene todas las substrings de A es la propia string A. Por lo tanto, para que la string B se reordene y contenga todas las substrings de A , debe contener A como substring. La string B reordenada puede contener A como su substring solo si la frecuencia de cada carácter en la string B es mayor o igual que su frecuencia en A . A continuación se muestran los pasos:
- Cuente la frecuencia de cada carácter en la string B en una array freq[] y luego reste las frecuencias de los caracteres correspondientes en la string A.
- Para formar lexicográficamente la string más pequeña, inicialice un resultado de string vacío y luego agréguele todos los caracteres sobrantes que tienen menos valor que el primer carácter de la string A .
- Antes de agregar todos los caracteres iguales al primer carácter A al resultado , verifique si hay algún carácter que sea menor que el primer carácter en la string A. Si es así, agregue A al resultado primero y luego todos los caracteres restantes iguales al primer carácter de A para hacer que la string reordenada sea lexicográficamente más pequeña.
- De lo contrario, agregue todas las ocurrencias restantes de A[0] y luego agregue A.
- Por último, agregue los caracteres restantes al resultado.
- Después de los pasos anteriores, imprima el resultado de la string .
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 reorder the string B
// to contain all the substrings of A
string reorderString(string A, string B)
{
// Find length of strings
int size_a = A.length();
int size_b = B.length();
// Initialize array to count the
// frequencies of the character
int freq[300] = { 0 };
// Counting frequencies of
// character in B
for (int i = 0; i < size_b; i++)
freq[B[i]]++;
// Find remaining character in B
for (int i = 0; i < size_a; i++)
freq[A[i]]--;
for (int j = 'a'; j <= 'z'; j++) {
if (freq[j] < 0)
return "-1";
}
// Declare the reordered string
string answer;
for (int j = 'a'; j < A[0]; j++)
// Loop until freq[j] > 0
while (freq[j] > 0) {
answer.push_back(j);
// Decrement the value
// from freq array
freq[j]--;
}
int first = A[0];
for (int j = 0; j < size_a; j++) {
// Check if A[j] > A[0]
if (A[j] > A[0])
break;
// Check if A[j] < A[0]
if (A[j] < A[0]) {
answer += A;
A.clear();
break;
}
}
// Append the remaining characters
// to the end of the result
while (freq[first] > 0) {
answer.push_back(first);
--freq[first];
}
answer += A;
for (int j = 'a'; j <= 'z'; j++)
// Push all the values from
// frequency array in the answer
while (freq[j]--)
answer.push_back(j);
// Return the answer
return answer;
}
// Driver Code
int main()
{
// Given strings A and B
string A = "aa";
string B = "ababab";
// Function Call
cout << reorderString(A, B);
return 0;
}
Java
// Java program for
// the above approach
class GFG{
// Function to reorder the String B
// to contain all the subStrings of A
static String reorderString(char []A,
char []B)
{
// Find length of Strings
int size_a = A.length;
int size_b = B.length;
// Initialize array to count the
// frequencies of the character
int freq[] = new int[300];
// Counting frequencies of
// character in B
for (int i = 0; i < size_b; i++)
freq[B[i]]++;
// Find remaining character in B
for (int i = 0; i < size_a; i++)
freq[A[i]]--;
for (int j = 'a'; j <= 'z'; j++)
{
if (freq[j] < 0)
return "-1";
}
// Declare the reordered String
String answer = "";
for (int j = 'a'; j < A[0]; j++)
// Loop until freq[j] > 0
while (freq[j] > 0)
{
answer+=j;
// Decrement the value
// from freq array
freq[j]--;
}
int first = A[0];
for (int j = 0; j < size_a; j++)
{
// Check if A[j] > A[0]
if (A[j] > A[0])
break;
// Check if A[j] < A[0]
if (A[j] < A[0])
{
answer += String.valueOf(A);
A = new char[A.length];
break;
}
}
// Append the remaining characters
// to the end of the result
while (freq[first] > 0)
{
answer += String.valueOf((char)first);
--freq[first];
}
answer += String.valueOf(A);
for (int j = 'a'; j <= 'z'; j++)
// Push all the values from
// frequency array in the answer
while (freq[j]-- > 0)
answer += ((char)j);
// Return the answer
return answer;
}
// Driver Code
public static void main(String[] args)
{
// Given Strings A and B
String A = "aa";
String B = "ababab";
// Function Call
System.out.print(reorderString(A.toCharArray(),
B.toCharArray()));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to reorder the B
# to contain all the substrings of A
def reorderString(A, B):
# Find length of strings
size_a = len(A)
size_b = len(B)
# Initialize array to count the
# frequencies of the character
freq = [0] * 300
# Counting frequencies of
# character in B
for i in range(size_b):
freq[ord(B[i])] += 1
# Find remaining character in B
for i in range(size_a):
freq[ord(A[i])] -= 1
for j in range(ord('a'), ord('z') + 1):
if (freq[j] < 0):
return "-1"
# Declare the reordered string
answer = []
for j in range(ord('a'), ord(A[0])):
# Loop until freq[j] > 0
while (freq[j] > 0):
answer.append(j)
# Decrement the value
# from freq array
freq[j] -= 1
first = A[0]
for j in range(size_a):
# Check if A[j] > A[0]
if (A[j] > A[0]):
break
# Check if A[j] < A[0]
if (A[j] < A[0]):
answer += A
A = ""
break
# Append the remaining characters
# to the end of the result
while (freq[ord(first)] > 0):
answer.append(first)
freq[ord(first)] -= 1
answer += A
for j in range(ord('a'), ord('z') + 1):
# Push all the values from
# frequency array in the answer
while (freq[j]):
answer.append(chr(j))
freq[j] -= 1
# Return the answer
return "".join(answer)
# Driver Code
if __name__ == '__main__':
# Given strings A and B
A = "aa"
B = "ababab"
# Function call
print(reorderString(A, B))
# This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to reorder the String B
// to contain all the subStrings of A
static String reorderString(char []A,
char []B)
{
// Find length of Strings
int size_a = A.Length;
int size_b = B.Length;
// Initialize array to count the
// frequencies of the character
int []freq = new int[300];
// Counting frequencies of
// character in B
for (int i = 0; i < size_b; i++)
freq[B[i]]++;
// Find remaining character in B
for (int i = 0; i < size_a; i++)
freq[A[i]]--;
for (int j = 'a'; j <= 'z'; j++)
{
if (freq[j] < 0)
return "-1";
}
// Declare the reordered String
String answer = "";
for (int j = 'a'; j < A[0]; j++)
// Loop until freq[j] > 0
while (freq[j] > 0)
{
answer+=j;
// Decrement the value
// from freq array
freq[j]--;
}
int first = A[0];
for (int j = 0; j < size_a; j++)
{
// Check if A[j] > A[0]
if (A[j] > A[0])
break;
// Check if A[j] < A[0]
if (A[j] < A[0])
{
answer += String.Join("", A);
A = new char[A.Length];
break;
}
}
// Append the remaining characters
// to the end of the result
while (freq[first] > 0)
{
answer += String.Join("", (char)first);
--freq[first];
}
answer += String.Join("", A);
for (int j = 'a'; j <= 'z'; j++)
// Push all the values from
// frequency array in the answer
while (freq[j]-- > 0)
answer += ((char)j);
// Return the answer
return answer;
}
// Driver Code
public static void Main(String[] args)
{
// Given Strings A and B
String A = "aa";
String B = "ababab";
// Function Call
Console.Write(reorderString(A.ToCharArray(),
B.ToCharArray()));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for
// the above approach
// Function to reorder the String B
// to contain all the subStrings of A
function reorderString(A,B)
{
// Find length of Strings
let size_a = A.length;
let size_b = B.length;
// Initialize array to count the
// frequencies of the character
let freq = new Array(300);
for(let i=0;i<300;i++)
{
freq[i]=0;
}
// Counting frequencies of
// character in B
for (let i = 0; i < size_b; i++)
freq[B[i].charCodeAt(0)]++;
// Find remaining character in B
for (let i = 0; i < size_a; i++)
freq[A[i].charCodeAt(0)]--;
for (let j = 'a'.charCodeAt(0); j <= 'z'.charCodeAt(0); j++)
{
if (freq[j] < 0)
return "-1";
}
// Declare the reordered String
let answer = "";
for (let j = 'a'.charCodeAt(0); j < A[0].charCodeAt(0); j++)
// Loop until freq[j] > 0
while (freq[j] > 0)
{
answer+=j;
// Decrement the value
// from freq array
freq[j]--;
}
let first = A[0];
for (let j = 0; j < size_a; j++)
{
// Check if A[j] > A[0]
if (A[j] > A[0])
break;
// Check if A[j] < A[0]
if (A[j] < A[0])
{
answer += (A).join("");
A = new Array(A.length);
break;
}
}
// Append the remaining characters
// to the end of the result
while (freq[first] > 0)
{
answer += (String.fromCharCode(first));
--freq[first];
}
answer += (A).join("");
for (let j = 'a'.charCodeAt(0); j <= 'z'.charCodeAt(0); j++)
// Push all the values from
// frequency array in the answer
while (freq[j]-- > 0)
answer += String.fromCharCode(j);
// Return the answer
return answer;
}
// Driver Code
// Given Strings A and B
let A = "aa";
let B = "ababab";
// Function Call
document.write(reorderString(A.split(""),
B.split("")));
// This code is contributed by patel2127
</script>
Producción:
aaabbb
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mysticpeaks y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA