Dadas dos strings A y B de longitud N y M respectivamente y una array arr[] que consta de K enteros, la tarea es verificar si la string B se puede obtener de la string A intercambiando cualquier par de caracteres adyacentes de la string A cualquier número de veces tal que los índices intercambiados no estén presentes en la array arr[] . Si es posible convertir la string A en la string B, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: A = “abcabka”, B = “acbakba”, arr[] = {0, 3, 6}
Salida: Sí
Explicación:
Intercambiar A 1 y A 2 . Ahora la string se convierte en A = “acbabka”.
Intercambiar A 4 y A 5 . Ahora la string se convierte en A = “acbakba”, que es lo mismo que la string B.Entrada: A = “aaa”, B = “bbb”, arr[] = {0}
Salida: No
Enfoque: siga los pasos a continuación para resolver el problema:
- Si la longitud de ambas strings no es igual, entonces la string A no se puede transformar en la string B. Por lo tanto, escriba “No” .
- Recorra la array dada arr[] y verifique si los caracteres en A[arr[i]] y B[arr[i]] son iguales o no. Si se encuentra que es cierto, escriba “No” . De lo contrario, realice los siguientes pasos:
- Si el primer elemento de arr[i] no es 0 :
- De manera similar, si el último elemento de arr[i] no es igual al elemento en el índice (N – 1) , entonces:
- Iterar un ciclo de 1 a N e inicializar dos punteros, L = arr[i – 1] y R = arr[i] :
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 frequency of the
// characters of two given strings
bool isEqual(string& A, string& B)
{
// Stores the frequencies of
// characters of strings A and B
map<char, int> mp, mp1;
// Traverse the string A
for (auto it : A) {
// Update frequency of
// each character
mp[it]++;
}
// Traverse the string B
for (auto it : B) {
// Update frequency of
// each character
mp1[it]++;
}
// Traverse the Map
for (auto it : mp) {
// If the frequency a character
// is not the same in both the strings
if (it.second != mp1[it.first]) {
return false;
}
}
return true;
}
// Function to check if it is possible
// to convert string A to string B
void IsPossible(string& A, string& B,
int arr[], int N)
{
// Base Case
if (A == B) {
cout << "Yes" << endl;
return;
}
// If length of both the
// strings are not equal
if (A.length() != B.length()) {
cout << "No" << endl;
return;
}
// Traverse the array and check
// if the blocked indices
// contains the same character
for (int i = 0; i < N; i++) {
int idx = arr[i];
// If there is a different
// character, return No
if (A[idx] != B[idx]) {
cout << "No" << endl;
return;
}
}
// If the first index is not present
if (arr[0]) {
string X = "";
string Y = "";
// Extract characters from
// string A and B
for (int i = 0; i < arr[0]; i++) {
X += A[i];
Y += B[i];
}
// If frequency is not same
if (!isEqual(A, B)) {
cout << "No" << endl;
return;
}
}
// If last index is not present
if (arr[N - 1] != (A.length() - 1)) {
string X = "";
string Y = "";
// Extract characters from
// string A and B
for (int i = arr[N - 1] + 1;
i < A.length(); i++) {
X += A[i];
Y += B[i];
}
// If frequency is not same
if (!isEqual(A, B)) {
cout << "No" << endl;
return;
}
}
// Traverse the array arr[]
for (int i = 1; i < N; i++) {
int L = arr[i - 1];
int R = arr[i];
string X = "";
string Y = "";
// Extract characters from strings A and B
for (int j = L + 1; j < R; j++) {
X += A[j];
Y += B[j];
}
// If frequency is not same
if (!isEqual(A, B)) {
cout << "No" << endl;
return;
}
}
// If all conditions are satisfied
cout << "Yes" << endl;
}
// Driver Code
int main()
{
string A = "abcabka";
string B = "acbakba";
int arr[] = { 0, 3, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
IsPossible(A, B, arr, N);
return 0;
}
Java
// Java program for the above approach
// importing input-output and utility classes
import java.io.*;
import java.util.*;
class GFG {
// method to count frequency of the
// characters of two given strings
static boolean isEqual(String A, String B)
{
// storing the frequencies of characters
HashMap<Character, Integer> map = new HashMap<>();
HashMap<Character, Integer> map2 = new HashMap<>();
// Traversing the String A
for (int i = 0; i < A.length(); i++) {
if (map.containsKey(A.charAt(i)))
map.put(A.charAt(i),
map.get(A.charAt(i)) + 1);
else
map.put(A.charAt(i), 1);
}
// Traversing the String B
for (int i = 0; i < B.length(); i++) {
if (map.containsKey(B.charAt(i)))
map.put(B.charAt(i),
map.get(B.charAt(i)) + 1);
else
map.put(B.charAt(i), 1);
}
// checking if both map have same character
// frequency
if (!map.equals(map2))
return false;
return true;
}
// method to check possibility to convert A into B
static void isPossible(String A, String B, int arr[],
int N)
{
// Base Case
if (A.equals(B)) {
System.out.println("Yes");
return;
}
// If length is not equal
if (A.length() != B.length()) {
System.out.println("No");
return;
}
for (int i = 0; i < N; i++) {
int idx = arr[i];
if (A.charAt(idx) != B.charAt(idx)) {
System.out.println("No");
return;
}
}
// If first index is not present
if (arr[0] == 0) {
String X = "";
String Y = "";
// Extracting Characters from A and B
for (int i = 0; i < arr[0]; i++) {
X += A.charAt(i);
Y += B.charAt(i);
}
// If frequency is not same
if (!isEqual(A, B)) {
System.out.println("No");
return;
}
}
// If last index is not present
if (arr[N - 1] != (A.length() - 1)) {
String X = "";
String Y = "";
for (int i = arr[N - 1] + 1; i < A.length();
i++) {
X += A.charAt(i);
Y += B.charAt(i);
}
if (!isEqual(A, B)) {
System.out.println("No");
return;
}
}
// Traversing the Array
for (int i = 1; i < N; i++) {
int L = arr[i - 1];
int R = arr[i - 1];
String X = "";
String Y = "";
// Extract Characters from Strings A and B
for (int j = L + 1; j < R; j++) {
X += A.charAt(j);
Y += B.charAt(j);
}
// if frequency is not same
if (!isEqual(A, B)) {
System.out.println("No");
return;
}
}
// if all condition satisfied
System.out.println("Yes");
}
// main method
public static void main(String[] args)
{
String A = "abcabka";
String B = "abcabka";
int arr[] = { 0, 3, 6 };
int N = arr.length;
// calling method
isPossible(A, B, arr, N);
}
}
Python3
# Python3 program for the above approach
from collections import defaultdict
# Function to count frequency of the
# characters of two given strings
def isEqual(A, B):
# Stores the frequencies of
# characters of strings A and B
mp = defaultdict(int)
mp1 = defaultdict(int)
# Traverse the string A
for it in A:
# Update frequency of
# each character
mp[it] += 1
# Traverse the string B
for it in B:
# Update frequency of
# each character
mp1[it] += 1
# Traverse the Map
for it in mp:
# If the frequency a character
# is not the same in both the strings
if (mp[it] != mp1[it]):
return False
return True
# Function to check if it is possible
# to convert string A to string B
def IsPossible(A, B, arr, N):
# Base Case
if (A == B):
print("Yes")
return
# If length of both the
# strings are not equal
if (len(A) != len(B)):
print("No")
return
# Traverse the array and check
# if the blocked indices
# contains the same character
for i in range(N):
idx = arr[i]
# If there is a different
# character, return No
if (A[idx] != B[idx]):
print("No")
return
# If the first index is not present
if (arr[0]):
X = ""
Y = ""
# Extract characters from
# string A and B
for i in range(arr[0]):
X += A[i]
Y += B[i]
# If frequency is not same
if (not isEqual(A, B)):
print("No")
return
# If last index is not present
if (arr[N - 1] != (len(A) - 1)):
X = ""
Y = ""
# Extract characters from
# string A and B
for i in range(arr[N - 1] + 1,
len(A)):
X += A[i]
Y += B[i]
# If frequency is not same
if (not isEqual(A, B)):
print("No")
return
# Traverse the array arr[]
for i in range(1, N):
L = arr[i - 1]
R = arr[i]
X = ""
Y = ""
# Extract characters from strings A and B
for j in range(L + 1, R):
X += A[j]
Y += B[j]
# If frequency is not same
if (not isEqual(A, B)):
print("No")
return
# If all conditions are satisfied
print("Yes")
# Driver Code
if __name__ == "__main__":
A = "abcabka"
B = "acbakba"
arr = [ 0, 3, 6 ]
N = len(arr)
IsPossible(A, B, arr, N)
# This code is contributed by ukasp
C#
// C# program for the above approach
// importing input-output and utility classes
using System;
using System.Collections.Generic;
class GFG
{
// method to count frequency of the
// characters of two given strings
static bool isEqual(string A, string B)
{
// storing the frequencies of characters
Dictionary<char, int> map
= new Dictionary<char, int>();
Dictionary<char, int> map2
= new Dictionary<char, int>();
// Traversing the String A
for (int i = 0; i < A.Length; i++) {
if (map.ContainsKey(A[i]))
map[A[i]] = map[A[i]] + 1;
else
map.Add(A[i], 1);
}
// Traversing the String B
for (int i = 0; i < B.Length; i++) {
if (map2.ContainsKey(B[i]))
map2[B[i]] = map2[B[i]] + 1;
else
map2.Add(B[i], 1);
}
// checking if both map have same character
// frequency
if (!map.Equals(map2))
return false;
return true;
}
// method to check possibility to convert A into B
static void isPossible(string A, string B, int[] arr,
int N)
{
// Base Case
if (A.Equals(B)) {
Console.WriteLine("Yes");
return;
}
// If length is not equal
if (A.Length != B.Length) {
Console.WriteLine("No");
return;
}
for (int i = 0; i < N; i++) {
int idx = arr[i];
if (A[idx] != B[idx]) {
Console.WriteLine("No");
return;
}
}
// If first index is not present
if (arr[0] == 0) {
String X = "";
String Y = "";
// Extracting Characters from A and B
for (int i = 0; i < arr[0]; i++) {
X += A[i];
Y += B[i];
}
// If frequency is not same
if (!isEqual(A, B)) {
Console.WriteLine("No");
return;
}
}
// If last index is not present
if (arr[N - 1] != (A.Length - 1)) {
string X = "";
string Y = "";
for (int i = arr[N - 1] + 1; i < A.Length;
i++) {
X += A[i];
Y += B[i];
}
if (!isEqual(A, B)) {
Console.WriteLine("No");
return;
}
}
// Traversing the Array
for (int i = 1; i < N; i++) {
int L = arr[i - 1];
int R = arr[i - 1];
string X = "";
string Y = "";
// Extract Characters from Strings A and B
for (int j = L + 1; j < R; j++) {
X += A[j];
Y += B[j];
}
// if frequency is not same
if (!isEqual(A, B)) {
Console.WriteLine("No");
return;
}
}
// if all condition satisfied
Console.WriteLine("Yes");
}
// main method
public static void Main()
{
string A = "abcabka";
string B = "abcabka";
int[] arr = { 0, 3, 6 };
int N = arr.Length;
// calling method
isPossible(A, B, arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to count frequency of the
// characters of two given strings
function isEqual(A, B)
{
// Stores the frequencies of
// characters of strings A and B
let mp = new Map();
let mp1 = new Map();
// Traverse the string A
for(let it of A)
{
// Update frequency of
// each character
if (mp.has(it))
{
mp.set(it, mp.get(it) + 1)
}
else
{
mp.set(it, 1)
}
}
// Traverse the string B
for(let it of B)
{
// Update frequency of
// each character
if (mp1.has(it))
{
mp1.set(it, mp1.get(it) + 1)
}
else
{
mp1.set(it, 1)
}
}
// Traverse the Map
for(let it of mp)
{
// If the frequency a character
// is not the same in both the strings
if (it[1] != mp1.get(it[0]))
{
return false;
}
}
return true;
}
// Function to check if it is possible
// to convert string A to string B
function IsPossible(A, B, arr, N)
{
// Base Case
if (A == B)
{
document.write("Yes" + "<br>");
return;
}
// If length of both the
// strings are not equal
if (A.length != B.length)
{
document.write("No" + "<br>");
return;
}
// Traverse the array and check
// if the blocked indices
// contains the same character
for(let i = 0; i < N; i++)
{
let idx = arr[i];
// If there is a different
// character, return No
if (A[idx] != B[idx])
{
document.write("No" + "<br>");
return;
}
}
// If the first index is not present
if (arr[0])
{
let X = "";
let Y = "";
// Extract characters from
// string A and B
for(let i = 0; i < arr[0]; i++)
{
X += A[i];
Y += B[i];
}
// If frequency is not same
if (!isEqual(A, B))
{
document.write("No" + "<br>");
return;
}
}
// If last index is not present
if (arr[N - 1] != (A.length - 1))
{
let X = "";
let Y = "";
// Extract characters from
// string A and B
for(let i = arr[N - 1] + 1;
i < A.length; i++)
{
X += A[i];
Y += B[i];
}
// If frequency is not same
if (!isEqual(A, B))
{
document.write("No" + "<br>");
return;
}
}
// Traverse the array arr[]
for(let i = 1; i < N; i++)
{
let L = arr[i - 1];
let R = arr[i];
let X = "";
let Y = "";
// Extract characters from strings A and B
for(let j = L + 1; j < R; j++)
{
X += A[j];
Y += B[j];
}
// If frequency is not same
if (!isEqual(A, B))
{
document.write("No" + "<br>");
return;
}
}
// If all conditions are satisfied
document.write("Yes" + "<br>");
}
// Driver Code
let A = "abcabka";
let B = "acbakba";
let arr = [ 0, 3, 6 ];
let N = arr.length
IsPossible(A, B, arr, N);
// This code is contributed by gfgking
</script>
Producción
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA