Dadas dos strings S1 y S2 , la tarea es verificar si la string S1 se puede igualar a la string S2 intercambiando cualquier par de caracteres que reemplace cualquier carácter en la string S1 . Si es posible hacer que la string S1 sea igual a S2 , imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S1 = “abc”, S2 = “bca”
Salida: Sí
Explicación:
Operación 1: “abc” -> “acb”
Operación 2: “acb” -> “bca”Entrada: S1 = “a”, S2 = “aa”
Salida: No
Explicación: Es imposible hacer que las dos strings sean iguales.
Enfoque: La idea para resolver este problema es encontrar las frecuencias de los caracteres en las strings y comprobar si se está utilizando el mismo carácter en ambas strings o no. Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays a[] y b[] para almacenar las frecuencias de las strings S1 y S2 .
- Atraviese las strings S1 y S2 y almacene las frecuencias de las strings en las arrays a[] y b[] .
- Ordene las arrays a[] y b[] .
- Recorra ambas arrays y si algún elemento es desigual en cualquier índice, imprima «No» , ya que hay al menos un carácter que es diferente en ambas strings.
- Después de los pasos anteriores, si no existe ninguna frecuencia desigual, imprima «Sí» , ya que la string S1 se puede convertir en la string S2 con las operaciones dadas.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find if given strings
// are same or not
bool sameStrings(string str1,
string str2)
{
int N = str1.length();
int M = str2.length();
// Base Condition
if (N != M) {
return false;
}
// Stores frequency of characters
// of the string str1 and str2
int a[256] = { 0 }, b[256] = { 0 };
// Traverse strings str1 & str2 and
// store frequencies in a[] and b[]
for (int i = 0; i < N; i++) {
a[str1[i] - 'a']++;
b[str2[i] - 'a']++;
}
// Check if both strings have
// same characters or not
int i = 0;
while (i < 256) {
if ((a[i] == 0 && b[i] == 0)
|| (a[i] != 0 && b[i] != 0)) {
i++;
}
// If a character is present
// in one string and is not in
// another string, return false
else {
return false;
}
}
// Sort the array a[] and b[]
sort(a, a + 256);
sort(b, b + 256);
// Check arrays a and b contain
// the same frequency or not
for (int i = 0; i < 256; i++) {
// If the frequencies are not
// the same after sorting
if (a[i] != b[i])
return false;
}
// At this point, str1 can
// be converted to str2
return true;
}
// Driver Code
int main()
{
string S1 = "cabbba", S2 = "abbccc";
if (sameStrings(S1, S2))
cout << "YES" << endl;
else
cout << " NO" << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find if given Strings
// are same or not
static boolean sameStrings(String str1,
String str2)
{
int N = str1.length();
int M = str2.length();
// Base Condition
if (N != M)
{
return false;
}
// Stores frequency of characters
// of the String str1 and str2
int []a = new int[256];
int []b = new int[256];
// Traverse Strings str1 & str2 and
// store frequencies in a[] and b[]
for (int i = 0; i < N; i++)
{
a[str1.charAt(i) - 'a']++;
b[str2.charAt(i) - 'a']++;
}
// Check if both Strings have
// same characters or not
int i = 0;
while (i < 256)
{
if ((a[i] == 0 && b[i] == 0)
|| (a[i] != 0 && b[i] != 0))
{
i++;
}
// If a character is present
// in one String and is not in
// another String, return false
else
{
return false;
}
}
// Sort the array a[] and b[]
Arrays.sort(a);
Arrays.sort(b);
// Check arrays a and b contain
// the same frequency or not
for (i = 0; i < 256; i++)
{
// If the frequencies are not
// the same after sorting
if (a[i] != b[i])
return false;
}
// At this point, str1 can
// be converted to str2
return true;
}
// Driver Code
public static void main(String[] args)
{
String S1 = "cabbba", S2 = "abbccc";
if (sameStrings(S1, S2))
System.out.print("YES" +"\n");
else
System.out.print(" NO" +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to find if given strings
# are same or not
def sameStrings(str1, str2):
N = len(str1)
M = len(str2)
# Base Condition
if (N != M):
return False
# Stores frequency of characters
# of the str1 and str2
a, b = [0]*256, [0]*256
# Traverse strings str1 & str2 and
# store frequencies in a[] and b[]
for i in range(N):
a[ord(str1[i]) - ord('a')] += 1
b[ord(str2[i]) - ord('a')] += 1
# Check if both strings have
# same characters or not
i = 0
while (i < 256):
if ((a[i] == 0 and b[i] == 0) or (a[i] != 0 and b[i] != 0)):
i += 1
# If a character is present
# in one and is not in
# another string, return false
else:
return False
# Sort the array a[] and b[]
a = sorted(a)
b = sorted(b)
# Check arrays a and b contain
# the same frequency or not
for i in range(256):
# If the frequencies are not
# the same after sorting
if (a[i] != b[i]):
return False
# At this point, str1 can
# be converted to str2
return True
# Driver Code
if __name__ == '__main__':
S1, S2 = "cabbba", "abbccc"
if (sameStrings(S1, S2)):
print("YES")
else:
print("NO")
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find if given Strings
// are same or not
static bool sameStrings(string str1,
string str2)
{
int N = str1.Length;
int M = str2.Length;
// Base Condition
if (N != M)
{
return false;
}
// Stores frequency of characters
// of the String str1 and str2
int []a = new int[256];
int []b = new int[256];
// Traverse Strings str1 & str2 and
// store frequencies in a[] and b[]
for (int j = 0; j < N; j++)
{
a[str1[j] - 'a']++;
b[str2[j] - 'a']++;
}
// Check if both Strings have
// same characters or not
int i = 0 ;
while (i < 256)
{
if ((a[i] == 0 && b[i] == 0)
|| (a[i] != 0 && b[i] != 0))
{
i++;
}
// If a character is present
// in one String and is not in
// another String, return false
else
{
return false;
}
}
// Sort the array a[] and b[]
Array.Sort(a);
Array.Sort(b);
// Check arrays a and b contain
// the same frequency or not
for (int j = 0; j < 256; j++)
{
// If the frequencies are not
// the same after sorting
if (a[j] != b[j])
return false;
}
// At this point, str1 can
// be converted to str2
return true;
}
// Driver Code
static public void Main()
{
string S1 = "cabbba", S2 = "abbccc";
if (sameStrings(S1, S2))
Console.Write("YES" +"\n");
else
Console.Write(" NO" +"\n");
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for the above approach
// Function to find if given Strings
// are same or not
function sameStrings(str1, str2) {
var N = str1.length;
var M = str2.length;
// Base Condition
if (N !== M) {
return false;
}
// Stores frequency of characters
// of the String str1 and str2
var a = new Array(256).fill(0);
var b = new Array(256).fill(0);
// Traverse Strings str1 & str2 and
// store frequencies in a[] and b[]
for (var j = 0; j < N; j++) {
a[str1[j].charCodeAt(0) - "a".charCodeAt(0)]++;
b[str2[j].charCodeAt(0) - "a".charCodeAt(0)]++;
}
// Check if both Strings have
// same characters or not
var i = 0;
while (i < 256) {
if ((a[i] === 0 && b[i] === 0) || (a[i] !== 0 && b[i] !== 0)) {
i++;
}
// If a character is present
// in one String and is not in
// another String, return false
else {
return false;
}
}
// Sort the array a[] and b[]
a.sort((x, y) => x - y);
b.sort((x, y) => x - y);
// Check arrays a and b contain
// the same frequency or not
for (var j = 0; j < 256; j++) {
// If the frequencies are not
// the same after sorting
if (a[j] !== b[j]) return false;
}
// At this point, str1 can
// be converted to str2
return true;
}
// Driver Code
var S1 = "cabbba",
S2 = "abbccc";
if (sameStrings(S1, S2)) document.write("YES" + "<br>");
else document.write(" NO" + "<br>");
</script>
Producción:
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(256)