Programa C++ para verificar si una string se puede formar a partir de otra string con un máximo de X cambios circulares en el sentido de las agujas del reloj

Dado un entero X y dos strings S1 y S2 , la tarea es verificar que la string S1 se pueda convertir en la string S2 cambiando los caracteres circularmente en el sentido de las agujas del reloj como máximo X veces.

Entrada: S1 = “abcd”, S2 = “dddd”, X = 3 
Salida: Sí 
Explicación: 
La string dada S1 se puede convertir en la string S2 como 
: Carácter “a” – Cambiar 3 veces – “d” 
Carácter “b” – Desplazar 2 veces – “d” 
Carácter “c” – Desplazar 1 vez – “d” 
Carácter “d” – Desplazar 0 veces – “d”

Entrada: S1 = “usted”, S2 = “ara”, X = 6 
Salida: Sí 
Explicación: 
La string dada S1 se puede convertir en la string S2 como – 
Carácter “y” – Desplazamiento circular 2 veces – “a” 
Carácter “o” – Desplazamiento 3 veces – “r” 
Carácter “u” – Desplazamiento circular 6 veces – “a”  

Enfoque: La idea es recorrer la string y para cada índice y encontrar la diferencia entre los valores ASCII del carácter en los índices respectivos de las dos strings. Si la diferencia es menor que 0, entonces para un cambio circular, suma 26 para obtener la diferencia real. Si para cualquier índice, la diferencia excede X , entonces S2 no se puede formar a partir de S1 , de lo contrario es posible. 
A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation to check
// that a given string can be
// converted to another string
// by circular clockwise shift
// of each character by atmost
// X times
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to check that all
// characters of s1 can be
// converted to s2 by circular
// clockwise shift atmost X times
void isConversionPossible(string s1,
                          string s2, int x)
{
    int diff, n;
    n = s1.length();
  
    // Check for all characters of
    // the strings whether the
    // difference between their
    // ascii values is less than
    // X or not
    for (int i = 0; i < n; i++) {
  
        // If both the characters
        // are same
        if (s1[i] == s2[i])
            continue;
  
        // Calculate the difference
        // between the ASCII values
        // of the characters
        diff = (int(s2[i] - s1[i])
                + 26)
               % 26;
  
        // If difference exceeds X
        if (diff > x) {
            cout << "NO" << endl;
            return;
        }
    }
  
    cout << "YES" << endl;
}
  
// Driver Code
int main()
{
    string s1 = "you";
    string s2 = "ara";
  
    int x = 6;
  
    // Function call
    isConversionPossible(s1, s2, x);
  
    return 0;
}

YES

Complejidad de tiempo: O(N),N=Longitud(S1)

Espacio Auxiliar: O(1)

¡ Consulte el artículo completo sobre Comprobar si se puede formar una string a partir de otra string con un máximo de X cambios circulares en el sentido de las agujas del reloj para obtener más detalles!