Dada una string Str de N caracteres y dos strings S1 y S2 de igual longitud donde S1[i] y S2[i] están relacionados entre sí, la tarea es encontrar la string lexicográficamente más pequeña que se puede obtener reemplazando caracteres en Str con su carácter afín.
Ejemplos:
Entrada: S1 = “rat”, S2 = “cbb”, Str = “trrb”
Salida: acca
Explicación: Para S1 y S2 dados, los caracteres que están relacionados entre sí son (r, c), (a, b ), y (t, b).
Por lo tanto, en la string dada, r puede reemplazarse por c;
b se puede reemplazar por a, y t se puede reemplazar por a.
Por lo tanto, Str = “bcca”. Aquí, b nuevamente puede ser reemplazada por a.
Por tanto, el valor final de Str = “acca”, que es el menor posible.Entrada: S1 = “abc”, S2 = “xyz”, Str = “pqr”
Salida: pqr
Enfoque ingenuo: el problema dado se puede resolver creando un gráfico no dirigido donde un borde que conecta (x, y) representa una relación entre los caracteres x e y . A partir de entonces, para cada carácter en la string dada , recorra el gráfico usando DFS y encuentre el carácter más pequeño entre los vértices conectados del carácter actual y reemplácelo.
Complejidad temporal: O(N * M), donde M representa el tamaño de S1 o S2.
Espacio auxiliar: O(M)
Enfoque eficiente: el enfoque anterior se puede resolver de manera óptima utilizando la estructura de datos de conjuntos disjuntos . La idea es agrupar todos los personajes que tienen una relación en un mismo grupo, lo que se puede hacer de manera eficiente usando DSU. Aquí, se puede observar que durante la operación de unión en DSU, el padre de un Node debe elegirse como el carácter más pequeño del grupo para lograr el orden lexicográfico más pequeño.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python code to implement the above approach
# Class to implements all functions
# of the Disjoint Set Data Structure
class DisjointSet:
def __init__(self):
self.size = 26
self.parent = [i for i in range(self.size)]
self.chars = [chr(i+97) for i in range(self.size)]
def find_parent(self, x):
if (self.parent[x] == x):
return (x)
self.parent[x] = self.find_parent(self.parent[x])
return (self.parent[x])
def union(self, u, v):
# find parent
p1 = self.find_parent(u)
p2 = self.find_parent(v)
# if not same
if (p1 != p2):
# if p2 smaller than p1
# then make parent p2
if (p2 < p1):
self.parent[p1] = p2
# make parent p1
else:
self.parent[p2] = p1
# Function to find the lexicographically
# smallest string formed by replacing
# characters according to given relation
def smallestLexStr(S1, S2, Str):
# Create an object of DSU
ds = DisjointSet()
M = len(S1)
# Iterate through all given relations
for i in range(M):
# find ascii value of each character
# and subtract from ascii value a
# so that index value between 0-25
idx1 = ord(S1[i]) - ord('a')
idx2 = ord(S2[i]) - ord('a')
# take union of both indices
ds.union(idx1, idx2)
# Convert String into list of characters
Str = list(Str)
# Iterate through the list of characters
for i in range(len(Str)):
# Find the smallest character
# replacement among all relations
idx = ds.find_parent(ord(Str[i]) - ord('a'))
Str[i] = ds.chars[idx]
# Convert the list back to a string
Str = "".join(Str)
# Return Answer
return Str
# Driver Code
if __name__ == "__main__":
S1 = "rat"
S2 = "cbb"
Str = "trrb"
print(smallestLexStr(S1, S2, Str))
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to find the lexicographically
// smallest string formed by replacing
// characters according to given relation
static string smallestLexStr(string S1, string S2, string Str){
// Create an object of DSU
DisjointSet ds = new DisjointSet();
int M = S1.Length;
// Iterate through all given relations
for (int i = 0 ; i < M ; i++){
// find ascii value of each character
// and subtract from ascii value a
// so that index value between 0-25
int idx1 = (int)(S1[i]) - (int)('a');
int idx2 = (int)(S2[i]) - (int)('a');
// take union of both indices
ds.union(idx1, idx2);
}
// Convert String into list of characters
List<char> arr = new List<char>(Str);
// Iterate through the list of characters
for (int i = 0 ; i < arr.Count ; i++){
// Find the smallest character
// replacement among all relations
int idx = ds.find_parent((int)(arr[i]) - (int)('a'));
arr[i] = ds.chars[idx];
}
// Convert the list back to a string
Str = "";
foreach (char x in arr){
Str += x;
}
// Return Answer
return Str;
}
// Driver code
public static void Main(string[] args){
string S1 = "rat";
string S2 = "cbb";
string Str = "trrb";
Console.WriteLine(smallestLexStr(S1, S2, Str));
}
}
// Class to implements all functions
// of the Disjoint Set Data Structure
public class DisjointSet{
public int size;
public int[] parent;
public char[] chars;
public DisjointSet(){
size = 26;
parent = new int[size];
for(int i = 0 ; i < size ; i++){
parent[i] = i;
}
chars = new char[size];
for(int i = 0 ; i < 26 ; i++){
chars[i] = (char)(i+97);
}
}
public int find_parent(int x){
if (parent[x] == x){
return x;
}
parent[x] = find_parent(parent[x]);
return (parent[x]);
}
public void union(int u, int v){
// find parent
int p1 = find_parent(u);
int p2 = find_parent(v);
// if not same
if (p1 != p2){
// if p2 smaller than p1
// then make parent p2
if (p2 < p1){
parent[p1] = p2;
// make parent p1
}else{
parent[p2] = p1;
}
}
}
}
// This code is contributed by subhamgoyal2014.
acca
Complejidad temporal: O(N)
Espacio auxiliar: O(1)