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:
- Primero, verifique si ambas strings ya son iguales o no. Si lo son, imprima Sí .
- Además, verifique si el tamaño de ambas strings es igual o no. Si no es así, imprima No.
- Cree un vector, digamos b y almacene los índices de carácter en la string B .
- Cree dos mapas, quédese mp1 y mp2 para almacenar la frecuencia de los caracteres en las strings A y B respectivamente.
- 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í.
- 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.
- De lo contrario, escriba No al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción
No
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sameergupta22 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA