Dada una string de alfabetos ingleses en minúsculas, encuentre el número de cambios de caracteres en sentido contrario a las agujas del reloj necesarios para formar el palíndromo de strings. Se da que desplazar la cuerda siempre dará como resultado el palíndromo.
Ejemplos:
Entrada: str = “baabbccb”
Salida: 2
Desplazando la cuerda en el sentido contrario a las agujas del reloj 2 veces,
hará que la cuerda sea un palíndromo.
1er turno: aabbccbb
2do turno: abbccbbaEntrada: bbaabbcc
Salida : 3
Desplazar la cuerda en el sentido contrario a las agujas del reloj
3 veces hará que la cuerda sea un palíndromo.
1er turno: baabbccb
2do turno: aabbccbb
3er turno: abbccbba
Enfoque ingenuo : un enfoque ingenuo es cambiar uno por uno el carácter de la string dada en sentido antihorario cíclicamente y verificar si la string es palíndromo o no.
Mejor enfoque : un mejor enfoque es agregar la string consigo misma e iterar desde el primer carácter hasta el último carácter de la string dada. La substring de i a i+n (donde i está en el rango [0, n-1]) en la string adjunta será la string obtenida después de cada cambio en sentido contrario a las agujas del reloj. Verifique la substring si es palíndromo o no. El número de operaciones de cambio será i.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find counter clockwise
// shifts to make string palindrome.
#include <bits/stdc++.h>
using namespace std;
// Function to check if given string is
// palindrome or not.
bool isPalindrome(string str, int l, int r)
{
while (l < r) {
if (str[l] != str[r])
return false;
l++;
r--;
}
return true;
}
// Function to find counter clockwise shifts
// to make string palindrome.
int CyclicShifts(string str)
{
int n = str.length();
// Pointer to starting of current
// shifted string.
int left = 0;
// Pointer to ending of current
// shifted string.
int right = n - 1;
// Concatenate string with itself
str = str + str;
// To store counterclockwise shifts
int cnt = 0;
// Move left and right pointers one
// step at a time.
while (right < 2 * n - 1) {
// Check if current shifted string
// is palindrome or not
if (isPalindrome(str, left, right))
break;
// If string is not palindrome
// then increase count of number
// of shifts by 1.
cnt++;
left++;
right++;
}
return cnt;
}
// Driver code.
int main()
{
string str = "bccbbaab";
cout << CyclicShifts(str);
return 0;
}
Java
// Java program to find counter clockwise
// shifts to make string palindrome.
class GFG {
// Function to check if given string is
// palindrome or not.
static boolean isPalindrome(String str, int l, int r)
{
while (l < r) {
if (str.charAt(l) != str.charAt(r))
return false;
l++;
r--;
}
return true;
}
// Function to find counter clockwise shifts
// to make string palindrome.
static int CyclicShifts(String str)
{
int n = str.length();
// Pointer to starting of current
// shifted string.
int left = 0;
// Pointer to ending of current
// shifted string.
int right = n - 1;
// Concatenate string with itself
str = str + str;
// To store counterclockwise shifts
int cnt = 0;
// Move left and right pointers one
// step at a time.
while (right < 2 * n - 1) {
// Check if current shifted string
// is palindrome or not
if (isPalindrome(str, left, right))
break;
// If string is not palindrome
// then increase count of number
// of shifts by 1.
cnt++;
left++;
right++;
}
return cnt;
}
// Driver code.
public static void main(String[] args)
{
String str = "bccbbaab";
System.out.println(CyclicShifts(str));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find counter clockwise # shifts to make string palindrome. # Function to check if given string # is palindrome or not. def isPalindrome(str, l, r): while (l < r) : if (str[l] != str[r]): return False l += 1 r -= 1 return True # Function to find counter clockwise # shifts to make string palindrome. def CyclicShifts(str): n = len(str) # Pointer to starting of current # shifted string. left = 0 # Pointer to ending of current # shifted string. right = n - 1 # Concatenate string with itself str = str + str # To store counterclockwise shifts cnt = 0 # Move left and right pointers # one step at a time. while (right < 2 * n - 1) : # Check if current shifted string # is palindrome or not if (isPalindrome(str, left, right)): break # If string is not palindrome # then increase count of number # of shifts by 1. cnt += 1 left += 1 right += 1 return cnt # Driver code. if __name__ == "__main__": str = "bccbbaab"; print(CyclicShifts(str)) # This code is contributed by ita_c
C#
// C# program to find counter clockwise
// shifts to make string palindrome.
using System;
class GFG
{
// Function to check if given string is
// palindrome or not.
static bool isPalindrome(String str, int l, int r)
{
while (l < r)
{
if (str[l] != str[r])
return false;
l++;
r--;
}
return true;
}
// Function to find counter clockwise shifts
// to make string palindrome.
static int CyclicShifts(String str)
{
int n = str.Length;
// Pointer to starting of current
// shifted string.
int left = 0;
// Pointer to ending of current
// shifted string.
int right = n - 1;
// Concatenate string with itself
str = str + str;
// To store counterclockwise shifts
int cnt = 0;
// Move left and right pointers one
// step at a time.
while (right < 2 * n - 1)
{
// Check if current shifted string
// is palindrome or not
if (isPalindrome(str, left, right))
break;
// If string is not palindrome
// then increase count of number
// of shifts by 1.
cnt++;
left++;
right++;
}
return cnt;
}
// Driver code.
public static void Main(String[] args)
{
String str = "bccbbaab";
Console.WriteLine(CyclicShifts(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find counter clockwise
// shifts to make string palindrome.
// Function to check if given string is
// palindrome or not.
function isPalindrome(str, l, r)
{
while (l < r) {
if (str[l] != str[r])
return false;
l++;
r--;
}
return true;
}
// Function to find counter clockwise shifts
// to make string palindrome.
function CyclicShifts(str)
{
var n = str.length;
// Pointer to starting of current
// shifted string.
var left = 0;
// Pointer to ending of current
// shifted string.
var right = n - 1;
// Concatenate string with itself
str = str + str;
// To store counterclockwise shifts
var cnt = 0;
// Move left and right pointers one
// step at a time.
while (right < 2 * n - 1) {
// Check if current shifted string
// is palindrome or not
if (isPalindrome(str, left, right))
break;
// If string is not palindrome
// then increase count of number
// of shifts by 1.
cnt++;
left++;
right++;
}
return cnt;
}
// Driver code.
var str = "bccbbaab";
document.write(CyclicShifts(str));
</script>
Producción:
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque Eficiente : Un enfoque eficiente es usar Hash Acumulativo . La string se desplaza cíclicamente según el método explicado anteriormente y el valor hash de esta string se compara con el valor hash de la string invertida. Si ambos valores son iguales, la string desplazada actual es un palíndromo; de lo contrario, la string se desplaza nuevamente. El conteo de turnos será i en cualquier paso. Para calcular el valor de ambas strings a continuación, se utiliza la función hash:
H(s) = ∑ (31 i * (S i – ‘a’)) % mod, 0 ≤ i ≤ (longitud de la string – 1)
donde, H(x) = Función hash
s = string dada
mod = 10 9 + 7
Itere todas las substrings y verifique si es un palíndromo o no usando la función hash indicada anteriormente y la técnica hash acumulativa.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find counter clockwise
// shifts to make string palindrome.
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
// Function that returns true
// if str is palindrome
bool isPalindrome(string str, int n)
{
int i = 0, j = n - 1;
while (i < j) {
if (str[i] != str[j])
return false;
i++;
j--;
}
return true;
}
// Function to find counter clockwise shifts
// to make string palindrome.
int CyclicShifts(string str)
{
int n = str.length(), i;
// If the string is already a palindrome
if (isPalindrome(str, n))
return 0;
// To store power of 31.
// po[i] = 31^i;
long long int po[2 * n + 2];
// To store hash value of string.
long long int preval[2 * n + 2];
// To store hash value of reversed
// string.
long long int suffval[2 * n + 2];
// To find hash value of string str[i..j]
long long int val1;
// To store hash value of reversed string
// str[j..i]
long long int val2;
// To store number of counter clockwise
// shifts.
int cnt = 0;
// Concatenate string with itself to shift
// it cyclically.
str = str + str;
// Calculate powers of 31 upto 2*n which
// will be used in hash function.
po[0] = 1;
for (i = 1; i <= 2 * n; i++) {
po[i] = (po[i - 1] * 31) % mod;
}
// Hash value of string str[0..i] is stored in
// preval[i].
for (i = 1; i <= 2 * n; i++) {
preval[i] = ((preval[i - 1] * 31) % mod + (str[i - 1] - 'a')) % mod;
}
// Hash value of string str[i..n-1] is stored
// in suffval[i].
for (i = 2 * n; i > 0; i--) {
suffval[i] = ((suffval[i + 1] * 31) % mod + (str[i - 1] - 'a')) % mod;
}
// Characters in string str[0..i] is present
// at position [(n-1-i)..(n-1)] in reversed
// string. If hash value of both are same
// then string is palindrome else not.
for (i = 1; i <= n; i++) {
// Hash value of shifted string starting at
// index i and ending at index i+n-1.
val1 = (preval[i + n - 1] - ((po[n] * preval[i - 1]) % mod)) % mod;
if (val1 < 0)
val1 += mod;
// Hash value of corresponding string when
// reversed starting at index i+n-1 and
// ending at index i.
val2 = (suffval[i] - ((po[n] * suffval[i + n])
% mod))
% mod;
if (val2 < 0)
val2 += mod;
// If both hash value are same then current
// string str[i..(i+n-1)] is palindrome.
// Else increase the shift count.
if (val1 != val2)
cnt++;
else
break;
}
return cnt;
}
// Driver code.
int main()
{
string str = "bccbbaab";
cout << CyclicShifts(str);
return 0;
}
Java
// Java program to find counter clockwise
// shifts to make string palindrome.
class GFG{
static int mod = 1000000007;
// Function that returns true
// if str is palindrome
public static boolean isPalindrome(String str, int n)
{
int i = 0, j = n - 1;
while (i < j)
{
if (str.charAt(i) != str.charAt(j))
return false;
i++;
j--;
}
return true;
}
// Function to find counter clockwise shifts
// to make string palindrome.
public static int CyclicShifts(String str)
{
int n = str.length(), i;
// If the string is already a palindrome
if (isPalindrome(str, n))
return 0;
// To store power of 31.
// po[i] = 31^i;
long[] po = new long[2 * n + 2];
// To store hash value of string.
long[] preval = new long[2 * n + 2];
// To store hash value of reversed
// string.
long[] suffval = new long[2 * n + 2];
// To find hash value of string str[i..j]
long val1;
// To store hash value of reversed string
// str[j..i]
long val2;
// To store number of counter clockwise
// shifts.
int cnt = 0;
// Concatenate string with itself to shift
// it cyclically.
str = str + str;
// Calculate powers of 31 upto 2*n which
// will be used in hash function.
po[0] = 1;
for(i = 1; i <= 2 * n; i++)
{
po[i] = (po[i - 1] * 31) % mod;
}
// Hash value of string str[0..i] is stored in
// preval[i].
for(i = 1; i <= 2 * n; i++)
{
preval[i] = ((preval[i - 1] * 31) % mod +
(str.charAt(i - 1) - 'a')) % mod;
}
// Hash value of string str[i..n-1] is stored
// in suffval[i].
for(i = 2 * n; i > 0; i--)
{
suffval[i] = ((suffval[i + 1] * 31) % mod +
(str.charAt(i - 1) - 'a')) % mod;
}
// Characters in string str[0..i] is present
// at position [(n-1-i)..(n-1)] in reversed
// string. If hash value of both are same
// then string is palindrome else not.
for(i = 1; i <= n; i++)
{
// Hash value of shifted string starting at
// index i and ending at index i+n-1.
val1 = (preval[i + n - 1] -
((po[n] *
preval[i - 1]) % mod)) % mod;
if (val1 < 0)
val1 += mod;
// Hash value of corresponding string when
// reversed starting at index i+n-1 and
// ending at index i.
val2 = (suffval[i] -
((po[n] *
suffval[i + n]) % mod)) % mod;
if (val2 < 0)
val2 += mod;
// If both hash value are same then current
// string str[i..(i+n-1)] is palindrome.
// Else increase the shift count.
if (val1 != val2)
cnt++;
else
break;
}
return cnt;
}
// Driver code
public static void main(String[] args)
{
String str = "bccbbaab";
System.out.println(CyclicShifts(str));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to find counter clockwise
# shifts to make string palindrome.
mod = 1000000007
# Function to find counter clockwise shifts
# to make string palindrome.
def CyclicShifts(str1):
n = len(str1)
i = 0
# To store power of 31.
# po[i] = 31 ^ i;
po = [0 for i in range(2 * n + 2)]
# To store hash value of string.
preval = [0 for i in range(2 * n + 2)]
# To store hash value of reversed
# string.
suffval = [0 for i in range(2 * n + 2)]
# To find hash value of string str[i..j]
val1 = 0
# To store hash value of reversed string
# str[j..i]
val2 = 0
# To store number of counter clockwise
# shifts.
cnt = 0
# Concatenate string with itself to shift
# it cyclically.
str1 = str1 + str1
# Calculate powers of 31 upto 2 * n which
# will be used in hash function.
po[0] = 1
for i in range(1, 2 * n + 1):
po[i] = (po[i - 1] * 31) % mod
# Hash value of string str[0..i]
# is stored in preval[i].
for i in range(1, 2 * n + 1):
preval[i] = ((preval[i - 1] * 31) % mod +
(ord(str1[i - 1]) -
ord('a'))) % mod
# Hash value of string str[i..n-1] is stored
# in suffval[i].
for i in range(2 * n, -1, -1):
suffval[i] = ((suffval[i + 1] * 31) % mod +
(ord(str1[i - 1]) -
ord('a'))) % mod
# Characters in string str[0..i] is present
# at position [(n-1-i)..(n-1)] in reversed
# string. If hash value of both are same
# then string is palindrome else not.
for i in range(1, n + 1):
# Hash value of shifted string starting at
# index i and ending at index i + n-1.
val1 = (preval[i + n - 1] - ((po[n] *
preval[i - 1]) % mod)) % mod
if (val1 < 0):
val1 += mod
# Hash value of corresponding string when
# reversed starting at index i + n-1 and
# ending at index i.
val2 = (suffval[i] - ((po[n] *
suffval[i + n])% mod)) % mod;
if (val2 < 0):
val2 += mod
# If both hash value are same then current
# string str[i..(i + n-1)] is palindrome.
# Else increase the shift count.
if (val1 != val2):
cnt += 1
else:
break
return cnt
# Driver code
str1 = "bccbbaab"
print(CyclicShifts(str1))
# This code is contributed by mohit kumar
C#
// C# program to find counter clockwise
// shifts to make string palindrome.
using System;
using System.Collections.Generic;
class GFG
{
static int mod= 1000000007;
// Function that returns true
// if str is palindrome
static bool isPalindrome(string str, int n)
{
int i = 0, j = n - 1;
while (i < j) {
if (str[i] != str[j])
return false;
i++;
j--;
}
return true;
}
// Function to find counter clockwise shifts
// to make string palindrome.
static int CyclicShifts(string str)
{
int n = str.Length, i;
// If the string is already a palindrome
if (isPalindrome(str, n))
return 0;
// To store power of 31.
// po[i] = 31^i;
long []po=new long[2 * n + 2];
// To store hash value of string.
long []preval=new long[2 * n + 2];
// To store hash value of reversed
// string.
long []suffval=new long[2 * n + 2];
// To find hash value of string str[i..j]
long val1;
// To store hash value of reversed string
// str[j..i]
long val2;
// To store number of counter clockwise
// shifts.
int cnt = 0;
// Concatenate string with itself to shift
// it cyclically.
str = str + str;
// Calculate powers of 31 upto 2*n which
// will be used in hash function.
po[0] = 1;
for (i = 1; i <= 2 * n; i++) {
po[i] = (po[i - 1] * 31) % mod;
}
// Hash value of string str[0..i] is stored in
// preval[i].
for (i = 1; i <= 2 * n; i++) {
preval[i] = ((preval[i - 1] * 31) % mod + (str[i - 1] - 'a')) % mod;
}
// Hash value of string str[i..n-1] is stored
// in suffval[i].
for (i = 2 * n; i > 0; i--) {
suffval[i] = ((suffval[i + 1] * 31) % mod + (str[i - 1] - 'a')) % mod;
}
// Characters in string str[0..i] is present
// at position [(n-1-i)..(n-1)] in reversed
// string. If hash value of both are same
// then string is palindrome else not.
for (i = 1; i <= n; i++) {
// Hash value of shifted string starting at
// index i and ending at index i+n-1.
val1 = (preval[i + n - 1] - ((po[n] * preval[i - 1]) % mod)) % mod;
if (val1 < 0)
val1 += mod;
// Hash value of corresponding string when
// reversed starting at index i+n-1 and
// ending at index i.
val2 = (suffval[i] - ((po[n] * suffval[i + n])
% mod))
% mod;
if (val2 < 0)
val2 += mod;
// If both hash value are same then current
// string str[i..(i+n-1)] is palindrome.
// Else increase the shift count.
if (val1 != val2)
cnt++;
else
break;
}
return cnt;
}
// Driver Code
public static void Main(string []args)
{
string str = "bccbbaab";
Console.Write(CyclicShifts(str));
}
}
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)