Dadas dos strings A y B , cada una de longitud N y un número entero K , la tarea es encontrar si la string A se puede convertir en string B , utilizando las siguientes operaciones cualquier número de veces:
- Tipo 1 : elija el índice i e intercambie A i y A i+1
- Tipo 2 : Elija el índice i , y si A i, A i+1 , …, A i+K-1 son todos iguales a algún carácter ch (ch ≠ z) , reemplace cada carácter con su siguiente carácter (ch+1) , por ejemplo: ‘d’ se reemplaza por ‘e’ y así sucesivamente.
Ejemplos:
Entrada: N = 4, A = «abba», B = «azza», K = 2
Salida: Sí
Explicación: Usando la segunda operación, podemos convertir los mismos caracteres a su siguiente carácter,
y así obtener la string B requerida
. abba” -> “acca” -> “adda” -> . . . -> “azza”Entrada: N = 2, A = “zz”, B = “aa”, K = 1
Salida: No
Enfoque: al observar la operación de type1 , es obvio que después de una secuencia finita de intercambios, la string se puede reordenar de cualquier forma. Por lo tanto, no hay necesidad de preocuparse de que los caracteres sean adyacentes durante la operación del segundo tipo (ya que el reordenamiento de las strings se puede hacer en cualquier momento), por lo que solo importa la frecuencia de los caracteres. Los siguientes son los pasos a seguir:
- Entonces, para convertir la string A en la string B , es necesario igualar las frecuencias de cada carácter del alfabeto y luego reordenar la string usando la operación de primer tipo .
- Si para cualquier carácter i , cualquier número insuficiente de ocurrencias ( frecuencia i, A < frecuencia i, B ) o si las ocurrencias restantes del carácter que no se pueden convertir en el siguiente carácter ( frecuencia i, A – frecuencia i, B ) no es un múltiplo de K (ya que para convertir el carácter a su siguiente longitud de carácter mayor que K se necesita), entonces la respuesta sería NO , de lo contrario SÍ .
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;
void solve(string& A, string& B, int& N,
int& K)
{
// Initializing two vectors to count
// frequency of two strings
int arr1[26] = { 0 }, arr2[26] = { 0 };
bool flag = true;
for (int i = 0; i < N; i++) {
arr1[A[i] - 'a']++;
arr2[B[i] - 'a']++;
}
int count = 0;
for (int i = 0; i < 26 && flag; i++) {
// Till 'y' is not encountered,
// say ch would be changed to ch+1
arr1[i] += count;
// Doing required operation to check
// if frequencies of each character
// of alphabet is atleast equal
if (arr1[i] >= arr2[i]) {
// Checking for case when
// remaining occurrences cannot be
// converted to next character
if ((arr1[i] - arr2[i]) % K) {
flag = false;
}
// Here, the characters from
// string A which were needed
// for string B are taken in count
count = arr1[i] - arr2[i];
continue;
}
else {
flag = false;
}
}
if (flag) {
cout << "Yes"
<< "\n";
}
else {
cout << "No"
<< "\n";
}
}
// Driver Code
int main()
{
string A = "zz", B = "aa";
int N = A.size();
int K = 1;
solve(A, B, N, K);
return 0;
}
Java
// Java program for the above approach
class GFG {
static void solve(String A, String B, int N, int K)
{
// Initializing two vectors to count
// frequency of two Strings
int[] arr1 = new int[26];
int[] arr2 = new int[26];
for (int i = 0; i < 26; i++) {
arr1[i] = 0;
arr2[i] = 0;
}
boolean flag = true;
for (int i = 0; i < N; i++) {
arr1[A.charAt(i) - 'a']++;
arr2[B.charAt(i) - 'a']++;
}
int count = 0;
for (int i = 0; i < 26 && flag; i++) {
// Till 'y' is not encountered,
// say ch would be changed to ch+1
arr1[i] += count;
// Doing required operation to check
// if frequencies of each character
// of alphabet is atleast equal
if (arr1[i] >= arr2[i]) {
// Checking for case when
// remaining occurences cannot be
// converted to next character
if ((arr1[i] - arr2[i]) % K == 1) {
flag = false;
}
// Here, the characters from
// String A which were needed
// for String B are taken in count
count = arr1[i] - arr2[i];
continue;
}
else {
flag = false;
}
}
if (flag) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
// Driver Code
public static void main(String args[])
{
String A = "zz", B = "aa";
int N = A.length();
int K = 1;
solve(A, B, N, K);
}
}
// This code is contributed by Saurabh Jaiswal
Python3
# Python code for the above approach
def solve(A, B, N, K):
# Initializing two vectors to count
# frequency of two strings
arr1 = [0] * 26
arr2 = [0] * 26
flag = True;
for i in range(N):
arr1[ord(A[i]) - ord('a')] += 1
arr2[ord(B[i]) - ord('a')] += 1
count = 0;
for i in range(26):
if(flag):
# Till 'y' is not encountered,
# say ch would be changed to ch+1
arr1[i] += count;
# Doing required operation to check
# if frequencies of each character
# of alphabet is atleast equal
if (arr1[i] >= arr2[i]):
# Checking for case when
# remaining occurences cannot be
# converted to next character
if ((arr1[i] - arr2[i]) % K):
flag = False;
# Here, the characters from
# string A which were needed
# for string B are taken in count
count = arr1[i] - arr2[i];
continue;
else:
flag = False;
if (flag):
print("Yes")
else:
print("No")
# Driver Code
A = "zz"
B = "aa";
N = len(A)
K = 1;
solve(A, B, N, K);
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG {
static void solve(string A, string B, int N, int K)
{
// Initializing two vectors to count
// frequency of two strings
int[] arr1 = new int[26];
int[] arr2 = new int[26];
for (int i = 0; i < 26; i++) {
arr1[i] = 0;
arr2[i] = 0;
}
bool flag = true;
for (int i = 0; i < N; i++) {
arr1[A[i] - 'a']++;
arr2[B[i] - 'a']++;
}
int count = 0;
for (int i = 0; i < 26 && flag; i++) {
// Till 'y' is not encountered,
// say ch would be changed to ch+1
arr1[i] += count;
// Doing required operation to check
// if frequencies of each character
// of alphabet is atleast equal
if (arr1[i] >= arr2[i]) {
// Checking for case when
// remaining occurences cannot be
// converted to next character
if ((arr1[i] - arr2[i]) % K == 1) {
flag = false;
}
// Here, the characters from
// string A which were needed
// for string B are taken in count
count = arr1[i] - arr2[i];
continue;
}
else {
flag = false;
}
}
if (flag) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
// Driver Code
public static void Main()
{
string A = "zz", B = "aa";
int N = A.Length;
int K = 1;
solve(A, B, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
function solve(A, B, N, K)
{
// Initializing two vectors to count
// frequency of two strings
let arr1 = new Array(26).fill(0);
let arr2 = new Array(26).fill(0);
let flag = true;
for (let i = 0; i < N; i++) {
arr1[A[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
arr2[B[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
let count = 0;
for (let i = 0; i < 26 && flag; i++) {
// Till 'y' is not encountered,
// say ch would be changed to ch+1
arr1[i] += count;
// Doing required operation to check
// if frequencies of each character
// of alphabet is atleast equal
if (arr1[i] >= arr2[i]) {
// Checking for case when
// remaining occurences cannot be
// converted to next character
if ((arr1[i] - arr2[i]) % K) {
flag = false;
}
// Here, the characters from
// string A which were needed
// for string B are taken in count
count = arr1[i] - arr2[i];
continue;
}
else {
flag = false;
}
}
if (flag) {
document.write("Yes" + "<br>")
}
else {
document.write("No" + "<br>")
}
}
// Driver Code
let A = "zz", B = "aa";
let N = A.length;
let K = 1;
solve(A, B, N, K);
// This code is contributed by Potta Lokesh
</script>
Producción
No
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por singhh3010 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA