String lexicográficamente más pequeña formada al reemplazar caracteres de acuerdo con la relación dada

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.
Producción

acca

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por chantya17 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *