Dado Two Strings s1 y s2 que contienen solo letras minúsculas de la misma longitud. La tarea es hacer que estas strings sean iguales usando el número mínimo de operaciones. En una sola operación puedes igualar cualquier letra a cualquier otro alfabeto.
Ejemplos:
Entrada: S1 = “abb”, S2 = “dad”
Salida: 2
a -> d
b -> a
Explicación:
Strings después de la primera operación –
S1 = “dbb”, S2 = “ddd”
Strings después de la segunda operación –
S1 = “ddd”, S2 = “ddd”Entrada: S1 = “bab”, S2 = “aab”
Salida: 1
b -> a
Explicación:
Strings después de la primera operación –
S1 = “aaa”, S2 = “aaa”
Enfoque: La idea es utilizar la estructura de datos de unión de conjuntos disjuntos . A continuación se muestra la ilustración de los pasos:
- Inicialice el padre de cada alfabeto a sí mismo.
- Recorra las dos strings simultáneamente con la ayuda del índice y verifique si los caracteres correspondientes tienen padres diferentes y luego combine la string que tiene menos rango en las strings.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum number of operations to
// make two strings equal
#include <bits/stdc++.h>
#define MAX 500001
using namespace std;
int parent[MAX];
int Rank[MAX];
// Function to find out
// parent of an alphabet
int find(int x)
{
return parent[x] =
parent[x] == x ? x :
find(parent[x]);
}
// Function to merge two
// different alphabets
void merge(int r1, int r2)
{
// Merge a and b using
// rank compression
if (r1 != r2) {
if (Rank[r1] > Rank[r2]) {
parent[r2] = r1;
Rank[r1] += Rank[r2];
}
else {
parent[r1] = r2;
Rank[r2] += Rank[r1];
}
}
}
// Function to find the minimum
// number of operations required
void minimumOperations(string s1,
string s2){
// Initializing parent to i
// and rank(size) to 1
for (int i = 1; i <= 26; i++) {
parent[i] = i;
Rank[i] = 1;
}
// We will store our
// answering this vector
vector<pair<char, char> > ans;
// Traversing strings
for (int i = 0; i < s1.length(); i++) {
if (s1[i] != s2[i]) {
// If they have different parents
if (find(s1[i] - 96) !=
find(s2[i] - 96)) {
// Find their respective
// parents and merge them
int x = find(s1[i] - 96);
int y = find(s2[i] - 96);
merge(x, y);
// Store this in
// our Answer vector
ans.push_back({ s1[i], s2[i] });
}
}
}
// Number of operations
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++)
cout << ans[i].first << "->"
<<ans[i].second << endl;
}
// Driver Code
int main()
{
// Two strings
// S1 and S2
string s1, s2;
s1 = "abb";
s2 = "dad";
// Function Call
minimumOperations(s1, s2);
return 0;
}
Java
// Java implementation to find the
// minimum number of operations to
// make two Strings equal
import java.util.*;
class GFG{
static final int MAX = 500001;
static int []parent = new int[MAX];
static int []Rank = new int[MAX];
static class pair
{
char first, second;
public pair(char first, char second)
{
this.first = first;
this.second = second;
}
}
// Function to find out
// parent of an alphabet
static int find(int x)
{
return parent[x] = parent[x] == x ? x :
find(parent[x]);
}
// Function to merge two
// different alphabets
static void merge(int r1, int r2)
{
// Merge a and b using
// rank compression
if (r1 != r2)
{
if (Rank[r1] > Rank[r2])
{
parent[r2] = r1;
Rank[r1] += Rank[r2];
}
else
{
parent[r1] = r2;
Rank[r2] += Rank[r1];
}
}
}
// Function to find the minimum
// number of operations required
static void minimumOperations(String s1,
String s2)
{
// Initializing parent to i
// and rank(size) to 1
for(int i = 1; i <= 26; i++)
{
parent[i] = i;
Rank[i] = 1;
}
// We will store our
// answer in this vector
Vector<pair> ans = new Vector<pair>();
// Traversing Strings
for(int i = 0; i < s1.length(); i++)
{
if (s1.charAt(i) != s2.charAt(i))
{
// If they have different parents
if (find(s1.charAt(i) - 96) !=
find(s2.charAt(i) - 96))
{
// Find their respective
// parents and merge them
int x = find(s1.charAt(i) - 96);
int y = find(s2.charAt(i) - 96);
merge(x, y);
// Store this in
// our Answer vector
ans.add(new pair(s1.charAt(i),
s2.charAt(i)));
}
}
}
// Number of operations
System.out.print(ans.size() + "\n");
for(int i = 0; i < ans.size(); i++)
System.out.print(ans.get(i).first + "->" +
ans.get(i).second +"\n");
}
// Driver Code
public static void main(String[] args)
{
// Two Strings
// S1 and S2
String s1, s2;
s1 = "abb";
s2 = "dad";
// Function call
minimumOperations(s1, s2);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation to find the # minimum number of operations to # make two strings equal MAX = 500001 parent = [0] * MAX Rank = [0] * MAX # Function to find out # parent of an alphabet def find(x): if parent[x] == x: return x else: return find(parent[x]) # Function to merge two # different alphabets def merge(r1, r2): # Merge a and b using # rank compression if(r1 != r2): if(Rank[r1] > Rank[r2]): parent[r2] = r1 Rank[r1] += Rank[r2] else: parent[r1] = r2 Rank[r2] += Rank[r1] # Function to find the minimum # number of operations required def minimumOperations(s1, s2): # Initializing parent to i # and rank(size) to 1 for i in range(1, 26 + 1): parent[i] = i Rank[i] = 1 # We will store our # answerin this list ans = [] # Traversing strings for i in range(len(s1)): if(s1[i] != s2[i]): # If they have different parents if(find(ord(s1[i]) - 96) != find(ord(s2[i]) - 96)): # Find their respective # parents and merge them x = find(ord(s1[i]) - 96) y = find(ord(s2[i]) - 96) merge(x, y) # Store this in # our Answer list ans.append([s1[i], s2[i]]) # Number of operations print(len(ans)) for i in ans: print(i[0], "->", i[1]) # Driver code if __name__ == '__main__': # Two strings # S1 and S2 s1 = "abb" s2 = "dad" # Function Call minimumOperations(s1, s2) # This code is contributed by Shivam Singh
C#
// C# implementation to find the
// minimum number of operations to
// make two Strings equal
using System;
using System.Collections.Generic;
class GFG{
static readonly int MAX = 500001;
static int []parent = new int[MAX];
static int []Rank = new int[MAX];
class pair
{
public char first, second;
public pair(char first, char second)
{
this.first = first;
this.second = second;
}
}
// Function to find out
// parent of an alphabet
static int find(int x)
{
return parent[x] = parent[x] ==
x ? x : find(parent[x]);
}
// Function to merge two
// different alphabets
static void merge(int r1, int r2)
{
// Merge a and b using
// rank compression
if (r1 != r2)
{
if (Rank[r1] > Rank[r2])
{
parent[r2] = r1;
Rank[r1] += Rank[r2];
}
else
{
parent[r1] = r2;
Rank[r2] += Rank[r1];
}
}
}
// Function to find the minimum
// number of operations required
static void minimumOperations(String s1,
String s2)
{
// Initializing parent to i
// and rank(size) to 1
for(int i = 1; i <= 26; i++)
{
parent[i] = i;
Rank[i] = 1;
}
// We will store our
// answer in this vector
List<pair> ans = new List<pair>();
// Traversing Strings
for(int i = 0; i < s1.Length; i++)
{
if (s1[i] != s2[i])
{
// If they have different parents
if (find(s1[i] - 96) !=
find(s2[i] - 96))
{
// Find their respective
// parents and merge them
int x = find(s1[i] - 96);
int y = find(s2[i] - 96);
merge(x, y);
// Store this in
// our Answer vector
ans.Add(new pair(s1[i],
s2[i]));
}
}
}
// Number of operations
Console.Write(ans.Count + "\n");
for(int i = 0; i < ans.Count; i++)
Console.Write(ans[i].first + "->" +
ans[i].second + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Two Strings
// S1 and S2
String s1, s2;
s1 = "abb";
s2 = "dad";
// Function call
minimumOperations(s1, s2);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation to find the
// minimum number of operations to
// make two strings equal
const MAX = 500001
let parent = new Array(MAX).fill(0)
Rank = new Array(MAX).fill(0)
// Function to find out
// parent of an alphabet
function find(x){
if(parent[x] == x)
return x
else
return find(parent[x])
}
// Function to merge two
// different alphabets
function merge(r1, r2){
// Merge a and b using
// rank compression
if(r1 != r2){
if(Rank[r1] > Rank[r2]){
parent[r2] = r1
Rank[r1] += Rank[r2]
}
else{
parent[r1] = r2
Rank[r2] += Rank[r1]
}
}
}
// Function to find the minimum
// number of operations required
function minimumOperations(s1, s2){
// Initializing parent to i
// and rank(size) to 1
for(let i = 2; i <= 26; i++)
{
parent[i] = i
Rank[i] = 1
}
// We will store our
// answerin this list
let ans = []
// Traversing strings
for(let i=0;i<s1.length;i++){
if(s1[i] != s2[i]){
// If they have different parents
if(find(s1.charCodeAt(i) - 96) != find(s2.charCodeAt(i) - 96)){
// Find their respective
// parents and merge them
let x = find(s1.charCodeAt(i) - 96)
let y = find(s2.charCodeAt(i) - 96)
merge(x, y)
// Store this in
// our Answer list
ans.push([s1[i], s2[i]])
}
}
}
// Number of operations
document.write(ans.length,"</br>")
for(let i of ans)
document.write(i[0], "->", i[1],"</br>")
}
// Driver code
// Two strings
// S1 and S2
let s1 = "abb"
let s2 = "dad"
// Function Call
minimumOperations(s1, s2)
// This code is contributed by Shinjan Patra
</script>
Producción:
2 a->d b->a
Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
Espacio Auxiliar: O(N).