Dadas dos strings str1 y str2 , la tarea es encontrar la permutación lexicográfica más pequeña de str1 que contiene str2 como una substring.
Nota : Suponga que la solución siempre existe.
Ejemplo:
Entrada: str1 = “abab”, str2 = “ab”
Salida: “aabb”
Explicación: La permutación lexicográficamente más pequeña de la string str1 es “aabb”, ya que “aabb” contiene la string “ab” como una substring, por lo tanto, “aabb ” es la respuesta requerida.Entrada: str1 = «geeksforgeeks», str2 = «para»
Salida: «eeeeforggkkss»
Enfoque: Este problema se puede resolver usando el concepto de la técnica de conteo de frecuencias . Siga los pasos a continuación para resolver este problema.
- Almacene la frecuencia de todos los caracteres de las strings str1 y str2 .
- Inicialice la string resultante con la substring.
- Resta la frecuencia de la segunda cuerda de la frecuencia de la primera cuerda
- Ahora, agregue los caracteres restantes que son lexicográficamente más pequeños o iguales que el primer carácter de la substring antes de la substring en la string resultante.
- Agregue los caracteres restantes en el orden lexicográfico detrás de la substring en la string resultante.
- Finalmente, imprima la string resultante.
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 print the desired
// lexicographic smaller string
string findSmallestString(string str1,
string str2)
{
int freq1[26], freq2[26];
memset(freq1, 0, sizeof freq1);
memset(freq2, 0, sizeof freq2);
// Calculate length of the string
int n1 = str1.length();
int n2 = str2.length();
// Stores the frequencies of
// characters of string str1
for (int i = 0; i < n1; ++i) {
freq1[str1[i] - 'a']++;
}
// Stores the frequencies of
// characters of string str2
for (int i = 0; i < n2; ++i) {
freq2[str2[i] - 'a']++;
}
// Decrease the frequency of
// second string from that of
// of the first string
for (int i = 0; i < 26; ++i) {
freq1[i] -= freq2[i];
}
// To store the resultant string
string res = "";
// To find the index of first
// character of the string str2
int minIndex = str2[0] - 'a';
// Append the characters in
// lexicographical order
for (int i = 0; i < 26; ++i) {
// Append all the current
// character (i + 'a')
for (int j = 0; j < freq1[i]; ++j) {
res += (char)(i + 'a');
}
// If we reach first character
// of string str2 append str2
if (i == minIndex) {
res += str2;
}
}
// Return the resultant string
return res;
}
// Driver Code
int main()
{
string str1 = "geeksforgeeksfor";
string str2 = "for";
cout << findSmallestString(str1, str2);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to print the desired
// lexicographic smaller String
static String findSmallestString(String str1,
String str2)
{
int []freq1 = new int[26];
int []freq2 = new int[26];
Arrays.fill(freq1, 0);
Arrays.fill(freq2, 0);
// Calculate length of the String
int n1 = str1.length();
int n2 = str2.length();
// Stores the frequencies of
// characters of String str1
for(int i = 0; i < n1; ++i)
{
freq1[str1.charAt(i) - 'a']++;
}
// Stores the frequencies of
// characters of String str2
for(int i = 0; i < n2; ++i)
{
freq2[str2.charAt(i) - 'a']++;
}
// Decrease the frequency of
// second String from that of
// of the first String
for(int i = 0; i < 26; ++i)
{
freq1[i] -= freq2[i];
}
// To store the resultant String
String res = "";
// To find the index of first
// character of the String str2
int minIndex = str2.charAt(0) - 'a';
// Append the characters in
// lexicographical order
for(int i = 0; i < 26; ++i)
{
// Append all the current
// character (i + 'a')
for(int j = 0; j < freq1[i]; ++j)
{
res += (char)(i + 'a');
}
// If we reach first character
// of String str2 append str2
if (i == minIndex)
{
res += str2;
}
}
// Return the resultant String
return res;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "geeksforgeeksfor";
String str2 = "for";
System.out.print(findSmallestString(str1, str2));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement
# the above approach
# Function to print the desired
# lexicographic smaller string
def findSmallestString(str1, str2):
freq1 = [0] * 26
freq2 = [0] * 26
# Calculate length of the string
n1 = len(str1)
n2 = len(str2)
# Stores the frequencies of
# characters of string str1
for i in range(n1):
freq1[ord(str1[i]) - ord('a')] += 1
# Stores the frequencies of
# characters of string str2
for i in range(n2):
freq2[ord(str2[i]) - ord('a')] += 1
# Decrease the frequency of
# second string from that of
# of the first string
for i in range(26):
freq1[i] -= freq2[i]
# To store the resultant string
res = ""
# To find the index of first
# character of the string str2
minIndex = ord(str2[0]) - ord('a')
# Append the characters in
# lexicographical order
for i in range(26):
# Append all the current
# character (i + 'a')
for j in range(freq1[i]):
res += chr(i+ ord('a'))
# If we reach first character
# of string str2 append str2
if i == minIndex:
res += str2
# Return the resultant string
return res
# Driver code
str1 = "geeksforgeeksfor"
str2 = "for"
print(findSmallestString(str1, str2))
# This code is contributed by Stuti Pathak
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to print the desired
// lexicographic smaller String
static String findSmallestString(String str1,
String str2)
{
int[] freq1 = new int[26];
int[] freq2 = new int[26];
// Calculate length of the String
int n1 = str1.Length;
int n2 = str2.Length;
// Stores the frequencies of
// characters of String str1
for (int i = 0; i < n1; ++i)
{
freq1[str1[i] - 'a']++;
}
// Stores the frequencies of
// characters of String str2
for (int i = 0; i < n2; ++i)
{
freq2[str2[i] - 'a']++;
}
// Decrease the frequency of
// second String from that of
// of the first String
for (int i = 0; i < 26; ++i)
{
freq1[i] -= freq2[i];
}
// To store the resultant String
String res = "";
// To find the index of first
// character of the String str2
int minIndex = str2[0] - 'a';
// Append the characters in
// lexicographical order
for (int i = 0; i < 26; ++i)
{
// Append all the current
// character (i + 'a')
for (int j = 0; j < freq1[i]; ++j)
{
res += (char)(i + 'a');
}
// If we reach first character
// of String str2 append str2
if (i == minIndex)
{
res += str2;
}
}
// Return the resultant String
return res;
}
// Driver Code
public static void Main(String[] args)
{
String str1 = "geeksforgeeksfor";
String str2 = "for";
Console.Write(findSmallestString(str1, str2));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to print the desired
// lexicographic smaller String
function findSmallestString(str1, str2)
{
let freq1 = Array.from({length: 26}, (_, i) => 0);
let freq2 = Array.from({length: 26}, (_, i) => 0);
// Calculate length of the String
let n1 = str1.length;
let n2 = str2.length;
// Stores the frequencies of
// characters of String str1
for (let i = 0; i < n1; ++i)
{
freq1[str1[i].charCodeAt() - 'a'.charCodeAt()]++;
}
// Stores the frequencies of
// characters of String str2
for (let i = 0; i < n2; ++i)
{
freq2[str2[i].charCodeAt() - 'a'.charCodeAt()]++;
}
// Decrease the frequency of
// second String from that of
// of the first String
for (let i = 0; i < 26; ++i)
{
freq1[i] -= freq2[i];
}
// To store the resultant String
let res = "";
// To find the index of first
// character of the String str2
let minIndex = str2[0].charCodeAt() - 'a'.charCodeAt();
// Append the characters in
// lexicographical order
for (let i = 0; i < 26; ++i)
{
// Append all the current
// character (i + 'a')
for (let j = 0; j < freq1[i]; ++j)
{
res += String.fromCharCode(i + 'a'.charCodeAt());
}
// If we reach first character
// of String str2 append str2
if (i == minIndex)
{
res += str2;
}
}
// Return the resultant String
return res;
}
// Driver code
let str1 = "geeksforgeeksfor";
let str2 = "for";
document.write(findSmallestString(str1, str2));
</script>
Producción:
eeeefforggkkorss
Complejidad temporal: O(N)
Espacio auxiliar: O(1)