Compruebe si dos strings no duplicadas se pueden igualar después de dos intercambios en una string como máximo

Dadas dos strings A y B que consisten en letras minúsculas únicas, la tarea es verificar si ambas strings se pueden igualar utilizando como máximo dos intercambios. Escriba Sí si pueden. De lo contrario , imprima No.

Ejemplo:

Entrada: A=”abcd”, B=”badc”
Salida: Sí
Primero intercambie a y b, y luego intercambie c y d, en la string A.
Entrada: A=”abcd”, B=”cbda”
Salida: No

Enfoque: en este problema, la string A solo se puede convertir en la string B si:

Caso 1: Si A ya es igual a B.
Caso 2: si el número de diferencias en ambas strings es inferior a 3 y ambas strings contienen el mismo carácter. Entonces siempre es posible crear B a partir de A.
Caso 3: si el número de diferencias es 4 y todos los pares de intercambio en la string A son iguales y opuestos en la string B.

Ahora, para resolver este problema, siga los pasos a continuación:

1. Primero, verifique si ambas strings ya son iguales o no. Si lo son, imprima Sí .
2. Además, verifique si el tamaño de ambas strings es igual o no. Si no es así, imprima No.
3. Cree un vector, digamos b y almacene los índices de carácter en la string B .
4. Cree dos mapas, quédese mp1 y mp2 para almacenar la frecuencia de los caracteres en las strings A y B respectivamente.
5. Ahora, verifique si el número de diferencias es menor o igual a 3 , y ambos mapas, mp1 y mp2 , tienen las mismas entradas. En caso afirmativo, entonces ambas strings se pueden hacer iguales. Entonces, imprime Sí.
6. Además, ambas strings se pueden hacer iguales si tienen 4 diferencias, pero si es un par de dos errores reflejados. Entonces, imprime Sí si las diferencias se reflejan en dos pares.
7. De lo contrario, escriba No al final.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if two strings can be made
// equal using at most two swaps
bool canBecomeEqual(string A, string B)
{
 
    if (A.size() != B.size()) {
        return 0;
    }
 
    // Case 1:
    if (A == B) {
        return 1;
    }
 
    // Vector to store the index of characters
    // in B
    vector<int> b(26, -1);
 
    for (int i = 0; i < A.size(); i++) {
        b[B[i] - 'a'] = i;
    }
 
    // Map to store the characters
    // with their frequencies
    unordered_map<char, int> mp1, mp2;
 
    // Variable to store
    // the total number of differences
    int diff = 0;
 
    // Set to store the pair of indexes
    // having changes in A wrt to B
    set<pair<int, int> > positions;
 
    for (int i = 0; i < A.size(); ++i) {
        if (A[i] != B[i]) {
            positions.insert({ i, b[A[i] - 'a'] });
            diff++;
        }
        mp1[A[i]]++;
        mp2[B[i]]++;
    }
 
    // Case 2:
    if (diff <= 3 and mp1 == mp2) {
        return 1;
    }
 
    // Case 3:
    if (diff == 4 and mp1 == mp2) {
        for (auto x : positions) {
            pair<int, int> search
                = { x.second, x.first };
 
            if (positions.find(search)
                == positions.end()) {
                return 0;
            }
        }
        return 1;
    }
 
    return 0;
}
 
// Driver Code
int main()
{
    string A = "abcd";
    string B = "cdba";
 
    if (canBecomeEqual(A, B)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

// Java code for the above approach
import java.util.*;
 
class GFG{
    static class pair
    {
        int first, second;
        public pair(int first, int second) 
        {
            this.first = first;
            this.second = second;
        }
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + first;
            result = prime * result + second;
            return result;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            pair other = (pair) obj;
            if (first != other.first)
                return false;
            if (second != other.second)
                return false;
            return true;
        }   
         
    }
   
// Function to check if two Strings can be made
// equal using at most two swaps
static boolean canBecomeEqual(String A, String B)
{
 
    if (A.length() != B.length()) {
        return false;
    }
 
    // Case 1:
    if (A == B) {
        return true;
    }
 
    // Vector to store the index of characters
    // in B
    int []b = new int[26];
 
    for (int i = 0; i < A.length(); i++) {
        b[B.charAt(i) - 'a'] = i;
    }
 
    // Map to store the characters
    // with their frequencies
    HashMap<Character,Integer> mp1, mp2;
    mp1 = new HashMap<Character,Integer>();
    mp2 = new HashMap<Character,Integer>();
   
    // Variable to store
    // the total number of differences
    int diff = 0;
 
    // Set to store the pair of indexes
    // having changes in A wrt to B
    HashSet<pair> positions = new HashSet<pair>();
 
    for (int i = 0; i < A.length(); ++i) {
        if (A.charAt(i) != B.charAt(i)) {
            positions.add(new pair(i, b[A.charAt(i) - 'a'] ));
            diff++;
        }
        if(mp1.containsKey(A.charAt(i))){
            mp1.put(A.charAt(i), mp1.get(A.charAt(i))+1);
        }
        else{
            mp1.put(A.charAt(i), 1);
        }
        if(mp2.containsKey(B.charAt(i))){
            mp2.put(B.charAt(i), mp2.get(B.charAt(i))+1);
        }
        else{
            mp2.put(B.charAt(i), 1);
        }
    }
 
    // Case 2:
    if (diff <= 3 && mp1 == mp2) {
        return true;
    }
 
    // Case 3:
    if (diff == 4 && mp1 == mp2) {
        for (pair x : positions) {
            pair search
                = new pair( x.second, x.first );
 
            if (!positions.contains(search)) {
                return false;
            }
        }
        return true;
    }
 
    return false;
}
 
// Driver Code
public static void main(String[] args)
{
    String A = "abcd";
    String B = "cdba";
 
    if (canBecomeEqual(A, B)) {
        System.out.print("Yes" +"\n");
    }
    else {
        System.out.print("No" +"\n");
    }
}
}
 
// This code is contributed by 29AjayKumar

# python3 code for the above approach
 
# Function to check if two strings can be made
# equal using at most two swaps
def canBecomeEqual(A, B):
 
    if (len(A) != len(B)):
        return 0
 
        # Case 1:
    if (A == B):
        return 1
 
        # Vector to store the index of characters
        # in B
    b = [-1 for _ in range(26)]
 
    for i in range(0, len(A)):
        b[ord(B[i]) - ord('a')] = i
 
        # Map to store the characters
        # with their frequencies
    mp1 = {}
    mp2 = {}
 
    # Variable to store
    # the total number of differences
    diff = 0
 
    # Set to store the pair of indexes
    # having changes in A wrt to B
    positions = set()
 
    for i in range(0, len(A)):
        if (A[i] != B[i]):
            positions.add((i, b[ord(A[i]) - ord('a')]))
            diff += 1
        if A[i] in mp1:
            mp1[A[i]] += 1
        else:
            mp1[A[i]] = 1
 
        if B[i] in mp2:
            mp2[B[i]] += 1
        else:
            mp2[B[i]] = 1
 
        # Case 2:
    if (diff <= 3 and mp1 == mp2):
        return 1
 
        # Case 3:
    if (diff == 4 and mp1 == mp2):
        for x in positions:
            search = (x[1], x[0])
            if (not (search in positions)):
                return 0
 
        return 1
 
    return 0
 
# Driver Code
if __name__ == "__main__":
 
    A = "abcd"
    B = "cdba"
 
    if (canBecomeEqual(A, B)):
        print("Yes")
 
    else:
        print("No")
 
    # This code is contributed by rakeshsahni

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
  class pair : IComparable<pair>
  {
    public int first, second;
    public pair(int first, int second)
    {
      this.first = first;
      this.second = second;
    }
    public int CompareTo(pair p)
    {
      return this.second-p.first;
    }
  }
 
  // Function to check if two Strings can be made
  // equal using at most two swaps
  static bool canBecomeEqual(String A, String B)
  {
 
    if (A.Length != B.Length) {
      return false;
    }
 
    // Case 1:
    if (A == B) {
      return true;
    }
 
    // List to store the index of characters
    // in B
    int []b = new int[26];
 
    for (int i = 0; i < A.Length; i++) {
      b[B[i] - 'a'] = i;
    }
 
    // Map to store the characters
    // with their frequencies
    Dictionary<char,int> mp1, mp2;
    mp1 = new Dictionary<char,int>();
    mp2 = new Dictionary<char,int>();
 
    // Variable to store
    // the total number of differences
    int diff = 0;
 
    // Set to store the pair of indexes
    // having changes in A wrt to B
    HashSet<pair> positions = new HashSet<pair>();
 
    for (int i = 0; i < A.Length; ++i) {
      if (A[i] != B[i]) {
        positions.Add(new pair(i, b[A[i] - 'a'] ));
        diff++;
      }
      if(mp1.ContainsKey(A[i])){
        mp1[A[i]] = mp1[A[i]]+1;
      }
      else{
        mp1.Add(A[i], 1);
      }
      if(mp2.ContainsKey(B[i])){
        mp2[B[i]] = mp2[B[i]]+1;
      }
      else{
        mp2.Add(B[i], 1);
      }
    }
 
    // Case 2:
    if (diff <= 3 && mp1 == mp2) {
      return true;
    }
 
    // Case 3:
    if (diff == 4 && mp1 == mp2) {
      foreach (pair x in positions) {
        pair search
          = new pair( x.second, x.first );
 
        if (!positions.Contains(search)) {
          return false;
        }
      }
      return true;
    }
 
    return false;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    String A = "abcd";
    String B = "cdba";
 
    if (canBecomeEqual(A, B)) {
      Console.Write("Yes" +"\n");
    }
    else {
      Console.Write("No" +"\n");
    }
  }
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript code for the above approach
 
// Function to check if two strings can be made
// equal using at most two swaps
function canBecomeEqual(A, B){
 
    if (A.length != B.length)
        return 0
 
    // Case 1:
    if (A.B)
        return 1
 
    // Vector to store the index of characters
    // in B
    let b = new Array(26).fill(-1)
 
    for(let i=0;i<A.length;i++){
        b[B.charCodeAt(i) - 'a'.charCodeAt(0)] = i
    }
 
    // Map to store the characters
    // with their frequencies
    let mp1 = new Map()
    let mp2 = new Map()
 
// Variable to store
// the total number of differences
    diff = 0
 
// Set to store the pair of indexes
// having changes in A wrt to B
    let positions = new Set()
 
    for(let i=0;i<A.length;i++){
        if (A[i] != B[i]){
            positions.add([i, b[A.charCodeAt(i) - 'a'.charCodeAt(0)]])
            diff += 1
        }
        if(mp1.has(A[i]))
            mp1.set(A[i],mp1.get(A[i])+1)
        else
            mp1.set(A[i],1)
 
        if(mp2.has(B[i]))
            mp2.set(B[i],mp2.get(B[i])+1)
        else
            mp2.set(B[i],1)
    }
 
    // Case 2:
    if (diff <= 3 && mp1 == mp2)
        return 1
 
    // Case 3:
    if (diff == 4 && mp1 == mp2){
        for(let x of positions){
            search = [x[1], x[0]]
            if (!positions.has(search))
                return 0
        }
 
        return 1
    }
 
    return 0
}
// Driver Code
 
let A = "abcd"
let B = "cdba"
 
if (canBecomeEqual(A, B))
    document.write("Yes")
 
else
    document.write("No")
 
// This code is contributed by shinjanpatra
 
</script>

No

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)