Número mínimo de pares necesarios para hacer dos cuerdas iguales

Dadas dos strings s1 y s2 de la misma longitud, la tarea es contar el número mínimo de pares de caracteres (c1, c2) de modo que al transformar c1 en c2 o c2 en c1 cualquier número de veces en cualquier string haga que ambas strings sean iguales . Ejemplos:

Entrada: s1 = “abb”, s2 = “papá” Salida: 2 Transformar ‘a’ -> ‘d’, ‘b’ -> ‘a’ y ‘b’ -> ‘a’ -> ‘d’ en s1 . No podemos tomar (a, d), (b, a), (b, d) como pares porque (b, d) se puede lograr siguiendo la transformación ‘b’ -> ‘a’ -> ‘d’ Entrada: s1 = “pimienta”, s2 = “cocacola” Salida: 7

Enfoque: este problema se puede resolver usando gráficos o conjuntos disjuntos. Construya un gráfico G vacío e itere a través de las strings. Agregue un borde en el gráfico G solo si se cumple una de las siguientes condiciones:

• Tanto s1[i] como s2[i] no están en G.
• s1[i] está en G pero s2[i] no está en G.
• s2[i] está en G pero s1[i] no está en G.
• No hay una ruta de s1[i] a s2[i] .

El número mínimo de pares será el conteo de aristas en el gráfico final G. A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function which will check if there is
// a path between a and b by using BFS
bool checkPath(char a, char b,
           map<char, vector<char>> &G)
{
    map<char, bool> visited;
    deque<char> queue;
    queue.push_back(a);
    visited[a] = true;
 
    while (!queue.empty())
    {
        int n = queue.front();
        queue.pop_front();
 
        if (n == b) return true;
        for (auto i : G[n])
        {
            if (visited[i] == false)
            {
                queue.push_back(i);
                visited[i] = true;
            }
        }
    }
    return false;
}
 
// Function to return the
// minimum number of pairs
int countPairs(string s1, string s2,
         map<char, vector<char>> &G, int x)
{
     
    // To store the count of pairs
    int count = 0;
 
    // Iterating through the strings
    for (int i = 0; i < x; i++)
    {
        char a = s1[i];
        char b = s2[i];
 
        // Check if we can add an edge in the graph
        if (G.find(a) != G.end() and
            G.find(b) == G.end() and a != b)
        {
            G[a].push_back(b);
            G[b].push_back(a);
            count++;
        }
        else if (G.find(b) != G.end() and
                 G.find(a) == G.end() and a != b)
        {
            G[b].push_back(a);
            G[a].push_back(b);
            count++;
        }
        else if (G.find(a) == G.end() and
                 G.find(b) == G.end() and a != b)
        {
            G[a].push_back(b);
            G[b].push_back(a);
            count++;
        }
        else
        {
            if (!checkPath(a, b, G) and a != b)
            {
                G[a].push_back(b);
                G[b].push_back(a);
                count++;
            }
        }
    }
 
    // Return the count of pairs
    return count;
}
 
// Driver Code
int main()
{
    string s1 = "abb", s2 = "dad";
    int x = s1.length();
    map<char, vector<char>> G;
    cout << countPairs(s1, s2, G, x) << endl;
 
    return 0;
}
 
// This code is contributed by
// sanjeev2552

# Python3 implementation of the approach
from collections import defaultdict, deque  
  
# Function which will check if there is
# a path between a and b by using BFS
def Check_Path(a, b, G):
    visited = defaultdict(bool)
    queue = deque()
    queue.append(a)
    visited[a]= True
    while queue:
        n = queue.popleft()
        if n == b:
            return True
        for i in list(G[n]):
            if visited[i]== False:
                queue.append(i)
                visited[i]= True
    return False
  
# Function to return the minimum number of pairs
def countPairs(s1, s2, G):
    name = defaultdict(bool)
     
    # To store the count of pairs
    count = 0
  
    # Iterating through the strings
    for i in range(x):
        a = s1[i]
        b = s2[i]
  
        # Check if we can add an edge in the graph
        if a in G and b not in G and a != b:
            G[a].append(b)
            G[b].append(a)
            count+= 1
        elif b in G and a not in G and a != b:
            G[b].append(a)
            G[a].append(b)
            count+= 1
        elif a not in G and b not in G and a != b:
            G[a].append(b)
            G[b].append(a)
            count+= 1
        else:
            if not Check_Path(a, b, G) and a != b:
                G[a].append(b)
                G[b].append(a)
                count+= 1
  
    # Return the count of pairs
    return count
  
# Driver code
if __name__=="__main__":
    s1 ="abb"
    s2 ="dad"
    x = len(s1)
    G = defaultdict(list)
    print(countPairs(s1, s2, G))

2

Complejidad de tiempo: O(x) donde x es la longitud de la primera string.

Complejidad espacial: O(x) donde x es la longitud de la string