Dé dos strings S1 y S2 , la tarea es verificar si la string S1 se puede igualar a la string S2 invirtiendo la substring de ambas strings de igual longitud.
Nota: una substring se puede invertir cualquier número de veces.
Ejemplo:
Entrada: S1 = “abbca”, S2 = “acabb”
Salida: Sí
Explicación:
La string S1 y S2 se pueden igualar mediante:
Invertir S1 en el rango [2, 4] (longitud = 3), S1 = “abacb”
Invierta S2 en el rango [1, 3] (longitud = 3), S2 = «abacb»
S1 = «abacb» y S2 = «abacb», después de invertir.
Por lo tanto, ambos pueden hacerse iguales.
Entrada: “ S1 = “abcd”, S2 = “abdc”
Salida: No
Acercarse:
- La idea es hacer que ambas strings sean iguales ordenándolas.
- Primero, verifique si ambas strings tienen el mismo conjunto de caracteres o no. Si no, entonces la respuesta es «No».
- Corrija la longitud de la substring para invertirla en 2. Ahora, esto significa intercambiar caracteres adyacentes.
- Ahora, el número de movimientos necesarios para ordenar una string invirtiendo la substring de tamaño 2 o, en otras palabras, intercambiando caracteres adyacentes, es el Recuento de inversión de la string.
- Si ambas strings tienen el mismo número de inversión, entonces la respuesta es «Sí».
- Si tienen diferentes recuentos de inversión, igualarlos solo es posible si al menos una de las siguientes condiciones coincide:
- Primero, si la paridad del conteo de inversión es la misma, es decir, par o impar, entonces la respuesta es «Sí». Continuaremos intercambiando cualquier par de elementos en la string ordenada hasta que se ordene el otro. Dado que la diferencia en el recuento de inversiones será uniforme, por lo que intercambiar cualquier par dos veces no produce ningún cambio.
- En segundo lugar, si la paridad no es la misma, entonces tiene que haber al menos un carácter con una frecuencia superior a 1 en cualquiera de las strings. Simplemente los intercambiaremos hasta que el otro se solucione. Dado que el intercambio de caracteres idénticos no produce ningún cambio.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// function to count inversion
// count of the string
int inversionCount(string& s)
{
// for storing frequency
int freq[26] = { 0 };
int inv = 0;
for (int i = 0; i < s.length(); i++) {
int temp = 0;
// Add all the characters which
// are less than the ith character
// before i.
for (int j = 0; j < int(s[i] - 'a'); j++)
// adding the count to inversion
// count
temp += freq[j];
inv += (i - temp);
// updating the character in
// the frequency array
freq[s[i] - 'a']++;
}
return inv;
}
// function to check whether any
// of the string have a repeated
// character
bool haveRepeated(string& S1,
string& S2)
{
int freq[26] = { 0 };
for (char i : S1) {
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
}
for (int i = 0; i < 26; i++)
freq[i] = 0;
for (char i : S2) {
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
}
return false;
}
// function to check whether the
// string S1 and S2 can be made
// equal by reversing sub strings
// of same size in both strings
void checkToMakeEqual(string S1,
string S2)
{
// frequency array to check
// whether both string have
// same character or not
int freq[26] = { 0 };
for (int i = 0; i < S1.length(); i++) {
// adding the frequency;
freq[S1[i] - 'a']++;
}
bool flag = 0;
for (int i = 0; i < S2.length(); i++) {
if (freq[S2[i] - 'a'] == 0) {
// if the character is not in S1
flag = true;
break;
}
// decrementing the frequency
freq[S2[i] - 'a']--;
}
if (flag == true) {
// If both string doesnot
// have same characters or not
cout << "No\n";
return;
}
// finding inversion count
// of both strings
int invCount1 = inversionCount(S1);
int invCount2 = inversionCount(S2);
if (invCount1 == invCount2
|| (invCount1 & 1) == (invCount2 & 1)
|| haveRepeated(S1, S2)) {
// If inversion count is same,
// or have same parity or if
// any of the string have a
// repeated character then
// the answer is Yes else No
cout << "Yes\n";
}
else
cout << "No\n";
}
// driver code
int main()
{
string S1 = "abbca", S2 = "acabb";
checkToMakeEqual(S1, S2);
return 0;
}
Python3
# Python3 program for the above approach
# function to count inversion
# count of the string
def inversionCount(s):
# for storing frequency
freq = [0 for _ in range(26)]
inv = 0
for i in range(len(s)):
# we'll add all the characters
# which are less than the ith
# character before i.
temp = 0
for j in range(ord(s[i]) - ord('a')):
# adding the count to
# inversion count
temp += freq[j]
inv += (i - temp)
# updating the character in
# the frequency array
freq[ord(s[i]) - ord('a')] += 1
return inv
# function to check whether
# any of the string have a
# repeated character
def haveRepeated(S1, S2):
freq = [0 for _ in range(26)]
for i in range(len(S1)):
if freq[ord(S1[i]) - ord('a')] > 0:
return 1
freq[ord(S1[i]) - ord('a')] += 1
for i in range(26):
freq[i] = 0
for i in range(len(S2)):
if freq[ord(S2[i]) - ord('a')] > 0:
return 1
freq[ord(S2[i]) - ord('a')] += 1
return 0
# function to check whether
# the string S1 and S2 can
# be made equal by reversing
# sub strings ofsame size in
# both strings
def checkToMakeEqual(S1, S2):
# frequency array to check
# whether both string have
# same character or not
freq = [0 for _ in range(26)]
for i in range(len(S1)):
# adding the frequency;
freq[ord(S1[i]) - ord('a')] += 1
flag = 0
for i in range(len(S2)):
if freq[ord(S2[i]) - ord('a')] == 0:
# if the character is not in S1
flag = 1
break
# decrementing the frequency
freq[ord(S2[i]) - ord('a')] -= 1
if flag == 1:
# If both string does not
# have same characters or not
print("No")
return
# finding inversion count of
# both strings
invCount1 = inversionCount(S1)
invCount2 = inversionCount(S2)
if ((invCount1 == invCount2) or
((invCount1 % 2) == (invCount2 % 2)) or
haveRepeated(S1, S2) == 1):
# If inversion count is same,
# or have same parity
# or if any of the string
# have a repeated character
# then the answer is Yes else No
print("Yes")
else:
print("No")
# Driver Code
S1 = "abbca"
S2 = "acabb"
checkToMakeEqual(S1, S2)
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to count inversion
// count of the string
static int inversionCount(String s)
{
// For storing frequency
int[] freq = new int[26];
int inv = 0;
for(int i = 0; i < s.length(); i++)
{
int temp = 0;
// Add all the characters which
// are less than the ith character
// before i.
for(int j = 0;
j < (int)(s.charAt(i) - 'a');
j++)
// Adding the count to inversion
// count
temp += freq[j];
inv += (i - temp);
// Updating the character in
// the frequency array
freq[s.charAt(i) - 'a']++;
}
return inv;
}
// Function to check whether any
// of the string have a repeated
// character
static boolean haveRepeated(String S1,
String S2)
{
int[] freq = new int[26];
for(char i : S1.toCharArray())
{
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
}
for(int i = 0; i < 26; i++)
freq[i] = 0;
for(char i : S2.toCharArray())
{
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
}
return false;
}
// Function to check whether the
// string S1 and S2 can be made
// equal by reversing sub strings
// of same size in both strings
static void checkToMakeEqual(String S1,
String S2)
{
// Frequency array to check
// whether both string have
// same character or not
int[] freq = new int[26];
for(int i = 0; i < S1.length(); i++)
{
// Adding the frequency;
freq[S1.charAt(i) - 'a']++;
}
boolean flag = false;
for(int i = 0; i < S2.length(); i++)
{
if (freq[S2.charAt(i) - 'a'] == 0)
{
// If the character is not in S1
flag = true;
break;
}
// Decrementing the frequency
freq[S2.charAt(i) - 'a']--;
}
if (flag == true)
{
// If both string doesnot
// have same characters or not
System.out.println("No");
return;
}
// Finding inversion count
// of both strings
int invCount1 = inversionCount(S1);
int invCount2 = inversionCount(S2);
if (invCount1 == invCount2 ||
(invCount1 & 1) == (invCount2 & 1) ||
haveRepeated(S1, S2))
{
// If inversion count is same,
// or have same parity or if
// any of the string have a
// repeated character then
// the answer is Yes else No
System.out.println("Yes");
}
else
System.out.println("No");
}
// Driver Code
public static void main (String[] args)
{
String S1 = "abbca", S2 = "acabb";
checkToMakeEqual(S1, S2);
}
}
// This code is contributed by offbeat
C#
// C# program for the above approach
using System;
class GFG{
// Function to count inversion
// count of the string
static int inversionCount(String s)
{
// For storing frequency
int[] freq = new int[26];
int inv = 0;
for(int i = 0; i < s.Length; i++)
{
int temp = 0;
// Add all the characters which
// are less than the ith character
// before i.
for(int j = 0;
j < (int)(s[i] - 'a');
j++)
// Adding the count to inversion
// count
temp += freq[j];
inv += (i - temp);
// Updating the character in
// the frequency array
freq[s[i] - 'a']++;
}
return inv;
}
// Function to check whether any
// of the string have a repeated
// character
static bool haveRepeated(String S1,
String S2)
{
int[] freq = new int[26];
foreach(char i in S1.ToCharArray())
{
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
}
for(int i = 0; i < 26; i++)
freq[i] = 0;
foreach(char i in S2.ToCharArray())
{
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
}
return false;
}
// Function to check whether the
// string S1 and S2 can be made
// equal by reversing sub strings
// of same size in both strings
static void checkToMakeEqual(String S1,
String S2)
{
// Frequency array to check
// whether both string have
// same character or not
int[] freq = new int[26];
for(int i = 0; i < S1.Length; i++)
{
// Adding the frequency;
freq[S1[i] - 'a']++;
}
bool flag = false;
for(int i = 0; i < S2.Length; i++)
{
if (freq[S2[i] - 'a'] == 0)
{
// If the character is not in S1
flag = true;
break;
}
// Decrementing the frequency
freq[S2[i] - 'a']--;
}
if (flag == true)
{
// If both string doesnot
// have same characters or not
Console.WriteLine("No");
return;
}
// Finding inversion count
// of both strings
int invCount1 = inversionCount(S1);
int invCount2 = inversionCount(S2);
if (invCount1 == invCount2 ||
(invCount1 & 1) == (invCount2 & 1) ||
haveRepeated(S1, S2))
{
// If inversion count is same,
// or have same parity or if
// any of the string have a
// repeated character then
// the answer is Yes else No
Console.WriteLine("Yes");
}
else
Console.WriteLine("No");
}
// Driver Code
public static void Main(String[] args)
{
String S1 = "abbca", S2 = "acabb";
checkToMakeEqual(S1, S2);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// function to count inversion
// count of the string
function inversionCount(s)
{
// For storing frequency
var freq = Array(26).fill(0);
var inv = 0;
for(var i = 0; i < s.length; i++)
{
var temp = 0;
// Add all the characters which
// are less than the ith character
// before i.
for(var j = 0;
j < String.fromCharCode(
s[i].charCodeAt(0) -
'a'.charCodeAt(0)); j++)
// Adding the count to inversion
// count
temp += freq[j];
inv += (i - temp);
// Updating the character in
// the frequency array
freq[s[i] - 'a']++;
}
return inv;
}
// Function to check whether any
// of the string have a repeated
// character
function haveRepeated(S1, S2)
{
var freq = Array(26).fill(0);
S1.forEach(i => {
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
});
for(var i = 0; i < 26; i++)
freq[i] = 0;
S2.split('').forEach(i => {
if (freq[i - 'a'] > 0)
return true;
freq[i - 'a']++;
});
return false;
}
// Function to check whether the
// string S1 and S2 can be made
// equal by reversing sub strings
// of same size in both strings
function checkToMakeEqual(S1, S2)
{
// Frequency array to check
// whether both string have
// same character or not
var freq = Array(26).fill(0);
for(var i = 0; i < S1.length; i++)
{
// Adding the frequency;
freq[S1[i] - 'a']++;
}
var flag = 0;
for(var i = 0; i < S2.length; i++)
{
if (freq[S2[i] - 'a'] == 0)
{
// If the character is not in S1
flag = true;
break;
}
// Decrementing the frequency
freq[S2[i] - 'a']--;
}
if (flag == true)
{
// If both string doesnot
// have same characters or not
document.write("No<br>");
return;
}
// Finding inversion count
// of both strings
var invCount1 = inversionCount(S1);
var invCount2 = inversionCount(S2);
if (invCount1 == invCount2 ||
(invCount1 & 1) == (invCount2 & 1) ||
haveRepeated(S1, S2))
{
// If inversion count is same,
// or have same parity or if
// any of the string have a
// repeated character then
// the answer is Yes else No
document.write("Yes<br>");
}
else
document.write("No<br>");
}
// Driver code
var S1 = "abbca", S2 = "acabb";
checkToMakeEqual(S1, S2);
// This code is contributed by itsok
</script>
Producción:
Yes
Complejidad del tiempo:
Space Complexity: 
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA