Количество сдвигов против часовой стрелки для создания палиндрома струны

Опубликовано: 24 Января, 2022

Для строки строчных английских алфавитов найдите количество сдвигов символов против часовой стрелки, необходимое для создания строкового палиндрома. Считается, что смещение строки всегда приводит к палиндрому.
Примеры:

Input: str = “baabbccb” 
Output: 2 
Shifting the string counterclockwise 2 times, 
will make the string palindrome. 
1st shift : aabbccbb 
2nd shift :abbccbba

Input: bbaabbcc 
Output: 3 
Shifting the string counterclockwise 
3 times will make the string palindrome. 
1st shift : baabbccb 
2nd shift : aabbccbb 
3rd shift : abbccbba

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход : наивный подход состоит в том, чтобы один за другим сдвигать символ заданной строки против часовой стрелки циклически и проверять, является ли строка палиндромом или нет.

Лучший подход : лучший подход - добавить строку с самой собой и выполнить итерацию от первого символа до последнего символа данной строки. Подстрокой от i до i + n (где i находится в диапазоне [0, n-1]) в добавленной строке будет строка, полученная после каждого сдвига против часовой стрелки. Проверьте подстроку, является ли она палиндромом или нет. Количество сменных операций будет i.

Below is the implementation of the above approach:

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>
Output: 
2

 

Сложность времени: O (N 2 )
Вспомогательное пространство: O (N)

Эффективный подход : эффективный подход - использовать кумулятивный хеш. Строка циклически сдвигается в соответствии с методом, описанным выше, и хеш-значение этой строки сравнивается с хеш-значением перевернутой строки. Если оба значения одинаковы, то текущая смещенная строка является палиндромом, в противном случае строка снова смещается. Количество смен будет i на любом этапе. Для вычисления значения обеих строк ниже используется хеш-функция:

H(s) = ∑ (31i * (Si – ‘a’)) % mod, 0 ≤ i ≤ (length of string – 1) 
where, H(x) = Hash function 
s = given string 
mod = 109 + 7 

Выполните итерации для всех подстрок и проверьте, является ли это палиндромом или нет, используя указанную выше хеш-функцию и метод кумулятивного хеширования.

Below is the implementation of the above approach: 

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
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022