Рубрики

Запросы по формированию подстроки палиндрома

Дана строка S и два типа запросов.

Type 1: 1 L x, Indicates update Lth index 
               of string S by x character.
Type 2: 2 L R, Find if characters between position L and R 
               of string, S can form a palindrome string. 
               If palindrome can be formed print "Yes", 
               else print "No".
1 <= L, R <= |S| 

Примеры:

Input : S = "geeksforgeeks"
Query 1: 1 4 g
Query 2: 2 1 4
Query 3: 2 2 3
Query 4: 1 10 t
Query 5: 2 10 11
Output :
Yes
Yes
No

Query 1: update index 3 (position 4) of string S by 
character 'g'. So new string S = "geegsforgeeks".

Query 2: find if rearrangement between index 0 and 3
can form a palindrome. "geegs" is palindrome, print "Yes".

Query 3: find if rearrangement between index 1 and 2 
can form a palindrome. "ee" is palindrome, print "Yes".

Query 4: update index 9 (position 10) of string S by 
character 't'. So new string S = "geegsforgteks".

Query 3: find if rearrangement between index 9 and 10 
can form a palindrome. "te" is not palindrome, print "No".

Подстрока S [L … R] образует палиндром только в том случае, если частоты всех символов в S [L … R] четные, за исключением одного, допустимого.

For query of type 1, simply update string 
S[L] by character x.

For each query of type 2, calculate the 
frequency of character and check if 
frequencies of all characters is even (with)
one exception allowed.

Ниже приведены два различных метода определения частоты каждого символа в S [L… R]:

Метод 1: Используйте массив частот, чтобы найти частоту каждого элемента в S [L… R].

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для запросов на подстроку палиндрома
// формирование.
#include <bits/stdc++.h>

using namespace std;

  
// Запрос типа 1: обновить строковую позицию i
// символ х.

void qType1(int l, int x, char str[])

{

    str[l - 1] = x;

}

  
// Вывести «Да», если диапазон [L..R] может образовывать палиндром,
// иначе выведите «Нет».

void qType2(int l, int r, char str[])

{

    int freq[27] = { 0 };

  

    // Находим частоту каждого символа в

    // S [L ... R].

    for (int i = l - 1; i <= r - 1; i++)

        freq[str[i] - 'a']++;

  

    // Проверка наличия более одного символа

    // частота больше 1.

    int count = 0;

    for (int j = 0; j < 26; j++)

        if (freq[j] % 2)

            count++;

  

    (count <= 1) ? (cout << "Yes" << endl) : (cout << "No" << endl);

}

  
// Управляемая программа

int main()

{

    char str[] = "geeksforgeeks";

    int n = strlen(str);

  

    qType1(4, 'g', str);

    qType2(1, 4, str);

    qType2(2, 3, str);

    qType1(10, 't', str);

    qType2(10, 11, str);

  

    return 0;

}

Джава

// Java-программа для запросов на подстроку
// формирование палиндрома.

  

class GFG {

  

    // Тип запроса 1: обновить строку

    // позиция i с символом x.

    static void qType1(int l, int x, char str[])

    {

        str[l - 1] = (char)x;

    }

  

    // Вывести «Да», если диапазон [L..R] может сформироваться

    // палиндром, иначе выведите «Нет».

    static void qType2(int l, int r, char str[])

    {

        int freq[] = new int[27];

  

        // Находим частоту каждого

        // символ в S [L ... R].

        for (int i = l - 1; i <= r - 1; i++) {

            freq[str[i] - 'a']++;

        }

  

        // Проверка, если больше чем один символ

        // иметь частоту больше 1.

        int count = 0;

        for (int j = 0; j < 26; j++) {

            if (freq[j] % 2 != 0) {

                count++;

            }

        }

        if (count <= 1) {

            System.out.println("Yes");

        }

        else {

            System.out.println("No");

        }

    }

  

    // Управляемый код

    public static void main(String[] args)

    {

        char str[] = "geeksforgeeks".toCharArray();

        int n = str.length;

  

        qType1(4, 'g', str);

        qType2(1, 4, str);

        qType2(2, 3, str);

        qType1(10, 't', str);

        qType2(10, 11, str);

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для запросов на подстроку
# формирование палиндрома.

  
# Тип запроса 1: обновить позицию str1ing
# я с символом х.

def qType1(l, x, str1):

    str1[l - 1] = x

  
# Pr "Да", если диапазон [L..R] может образовывать палиндром,
# еще пр "Нет".

def qType2(l, r, str1):

  

    freq = [0 for i in range(27)] 

  

    # Найти частоту

    # каждый символ в S [L ... R].

    for i in range(l - 1, r):

        freq[ord(str1[i]) - ord('a')] += 1

  

    # Проверка, если больше чем один символ

    # имеют частоту больше 1.

    count = 0

    for j in range(26):

        if (freq[j] % 2):

            count += 1

    if count <= 1:

        print("Yes")

    else:

        print("No")

  
Код водителя

str1 = "geeksforgeeks"

str2 = [i for i in str1]

n = len(str2)

  

qType1(4, 'g', str2)

qType2(1, 4, str2)

qType2(2, 3, str2)

qType1(10, 't', str2)

qType2(10, 11, str2)

  
# Этот код предоставлен Мохит Кумар

C #

// C # программа для запросов на подстроку
// формирование палиндрома.

using System;

  

class GFG {

  

    // Тип запроса 1: обновить строку

    // позиция i с символом x.

    static void qType1(int l, int x, char[] str)

    {

        str[l - 1] = (char)x;

    }

  

    // Вывести «Да», если диапазон [L..R] может сформироваться

    // палиндром, иначе выведите «Нет».

    static void qType2(int l, int r, char[] str)

    {

        int[] freq = new int[27];

  

        // Находим частоту каждого

        // символ в S [L ... R].

        for (int i = l - 1; i <= r - 1; i++) {

            freq[str[i] - 'a']++;

        }

  

        // Проверка, если больше чем один символ

        // иметь частоту больше 1.

        int count = 0;

        for (int j = 0; j < 26; j++) {

            if (freq[j] % 2 != 0) {

                count++;

            }

        }

        if (count <= 1) {

            Console.WriteLine("Yes");

        }

        else {

            Console.WriteLine("No");

        }

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        char[] str = "geeksforgeeks".ToCharArray();

        int n = str.Length;

  

        qType1(4, 'g', str);

        qType2(1, 4, str);

        qType2(2, 3, str);

        qType1(10, 't', str);

        qType2(10, 11, str);

    }

}

  
// Этот код предоставлен Rajput-Ji

PHP

<?php
// PHP-программа для запросов на подстроку палиндрома
// формирование.

  
// Запрос типа 1: обновить строковую позицию i
// символ х.

function qType1($l, $x, &$str)

{

    $str[$l - 1] = $x;

}

  
// Вывести «Да», если диапазон [L..R] может образовывать палиндром,
// иначе выведите «Нет».

function qType2($l, $r, $str)

{

    $freq=array_fill(0, 27, 0);

  

    // Находим частоту каждого символа в

    // S [L ... R].

    for ($i = $l - 1; $i <= $r - 1; $i++)

        $freq[ord($str[$i]) - ord('a')]++;

  

    // Проверка наличия более одного символа

    // частота больше 1.

    $count = 0;

    for ($j = 0; $j < 26; $j++)

        if ($freq[$j] % 2)

            $count++;

  

    ($count <= 1) ? (print("Yes\n")) : (print("No\n"));

}

  
// Код драйвера

    $str = "geeksforgeeks";

    $n = strlen($str);

  

    qType1(4, 'g', $str);

    qType2(1, 4, $str);

    qType2(2, 3, $str);

    qType1(10, 't', $str);

    qType2(10, 11, $str);

  
// Этот код предоставлен mits
?>


Выход:

Yes
Yes
No

Способ 2: использовать двоичное индексированное дерево
Эффективным подходом может быть поддержание 26 двоичных индексов для каждого алфавита.
Определите функцию getFrequency (i, u), которая возвращает частоту 'u' в i- м префиксе. Частоту символа 'u' в диапазоне L… R можно найти с помощью getFrequency (R, u) — getFrequency (L-1, u).
Всякий раз, когда происходит обновление (Query 1), чтобы изменить S [i] с символа 'u' на 'v'. BIT [u] обновляется с -1 по индексу i, а BIT [v] обновляется с +1 по индексу i.

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для запросов на подстроку палиндрома
// формирование.
#include <bits/stdc++.h>
#define max 1000

using namespace std;

  
// Возвращаем частоту символа в
// i-й префикс.

int getFrequency(int tree[max][27], int idx, int i)

{

    int sum = 0;

  

    while (idx > 0) {

        sum += tree[idx][i];

        idx -= (idx & -idx);

    }

  

    return sum;

}

  
// Обновление BIT

void update(int tree[max][27], int idx, int val, int i)

{

    while (idx <= max) {

        tree[idx][i] += val;

        idx += (idx & -idx);

    }

}

  
// Запрос на обновление символа в строке.

void qType1(int tree[max][27], int l, int x, char str[])

{

    // Добавляем -1 в позицию L

    update(tree, l, -1, str[l - 1] - 97 + 1);

  

    // Обновление персонажа

    str[l - 1] = x;

  

    // Добавляем +1 в позицию R

    update(tree, l, 1, str[l - 1] - 97 + 1);

}

  
// Запрос, чтобы найти перестановку символа в диапазоне
// L ... R может образовывать палиндром

void qType2(int tree[max][27], int l, int r, char str[])

{

    int count = 0;

  

    for (int i = 1; i <= 26; i++) {

        // Проверка первого символа строки S.

        if (l == 1) {

            if (getFrequency(tree, r, i) % 2 == 1)

                count++;

        }

        else {

            // Проверка, является ли частота символа четной или нечетной.

            if ((getFrequency(tree, r, i) - getFrequency(tree, l - 1, i)) % 2 == 1)

                count++;

        }

    }

  

    (count <= 1) ? (cout << "Yes" << endl) : (cout << "No" << endl);

}

  
// Создание бинарного дерева индексов всего алфавита

void buildBIT(int tree[max][27], char str[], int n)

{

    memset(tree, 0, sizeof(tree));

  

    for (int i = 0; i < n; i++)

        update(tree, i + 1, 1, str[i] - 97 + 1);

}

  
// Управляемая программа

int main()

{

    char str[] = "geeksforgeeks";

    int n = strlen(str);

  

    int tree[max][27];

    buildBIT(tree, str, n);

  

    qType1(tree, 4, 'g', str);

    qType2(tree, 1, 4, str);

    qType2(tree, 2, 3, str);

    qType1(tree, 10, 't', str);

    qType2(tree, 10, 11, str);

  

    return 0;

}

Джава

// Java-программа для запросов на подстроку палиндрома
// формирование.

  

import java.util.*;

  

class GFG {

  

    static int max = 1000;

  

    // Возвращаем частоту символа в

    // i-й префикс.

    static int getFrequency(int tree[][], int idx, int i)

    {

        int sum = 0;

  

        while (idx > 0) {

            sum += tree[idx][i];

            idx -= (idx & -idx);

        }

  

        return sum;

    }

  

    // Обновление BIT

    static void update(int tree[][], int idx,

                       int val, int i)

    {

        while (idx <= max) {

            tree[idx][i] += val;

            idx += (idx & -idx);

        }

    }

  

    // Запрос на обновление символа в строке.

    static void qType1(int tree[][], int l, int x, char str[])

    {

        // Добавляем -1 в позицию L

        update(tree, l, -1, str[l - 1] - 97 + 1);

  

        // Обновление персонажа

        str[l - 1] = (char)x;

  

        // Добавляем +1 в позицию R

        update(tree, l, 1, str[l - 1] - 97 + 1);

    }

  

    // Запрос, чтобы найти перестановку символа в диапазоне

    // L ... R может образовывать палиндром

    static void qType2(int tree[][], int l, int r, char str[])

    {

        int count = 0;

  

        for (int i = 1; i <= 26; i++) {

            // Проверка первого символа строки S.

            if (l == 1) {

                if (getFrequency(tree, r, i) % 2 == 1)

                    count++;

            }

            else {

                // Проверка, является ли частота символа четной или нечетной.

                if ((getFrequency(tree, r, i) - getFrequency(tree, l - 1, i)) % 2 == 1)

                    count++;

            }

        }

  

        if (count <= 1)

            System.out.println("Yes");

        else

            System.out.println("No");

    }

  

    // Создание бинарного дерева индексов всего алфавита

    static void buildBIT(int tree[][], char str[], int n)

    {

  

        for (int i = 0; i < n; i++)

            update(tree, i + 1, 1, str[i] - 97 + 1);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        char str[] = "geeksforgeeks".toCharArray();

        int n = str.length;

  

        int tree[][] = new int[max][27];

        buildBIT(tree, str, n);

  

        qType1(tree, 4, 'g', str);

        qType2(tree, 1, 4, str);

        qType2(tree, 2, 3, str);

        qType1(tree, 10, 't', str);

        qType2(tree, 10, 11, str);

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

python3

# Python3 программа для запросов на подстановку палиндрома
# формирование.

  

max = 1000;

  
# Вернуть частоту символа в
# i-й префикс.

def getFrequency(tree, idx, i):

    sum = 0;

  

    while (idx > 0):

        sum += tree[idx][i];

        idx -= (idx & -idx);

  

    return sum;

  
# Обновление BIT

def update(tree, idx, val, i):

    while (idx <= max):

        tree[idx][i] += val;

        idx += (idx & -idx);

  
# Запрос на обновление символа в строке.

def qType1(tree, l, x, str1):

  

    # Добавление -1 в позиции L

    update(tree, l, -1, ord(str1[l - 1]) - 97 + 1);

  

    # Обновление персонажа

    list1 = list(str1)

    list1[l - 1] = x;

    str1 = ''.join(list1);

  

    # Добавление +1 в позиции R

    update(tree, l, 1, ord(str1[l - 1]) - 97 + 1);

  
# Запрос, чтобы найти, если перестановка символов в диапазоне
# L ... R может образовывать палиндром

def qType2(tree, l, r, str1):

    count = 0;

  

    for i in range(1, 27):

          

        # Проверка по первому символу строки S.

        if (l == 1):

            if (getFrequency(tree, r, i) % 2 == 1):

                count+=1;

        else:

            # Проверка, является ли частота символа четной или нечетной.

            if ((getFrequency(tree, r, i) - 

                getFrequency(tree, l - 1, i)) % 2 == 1):

                count += 1;

  

    print("Yes") if(count <= 1) else print("No");

  
# Создание бинарного дерева индексов всего алфавита

def buildBIT(tree,str1, n):

  

    for i in range(n):

        update(tree, i + 1, 1, ord(str1[i]) - 97 + 1);

  
# Код драйвера

  

str1 = "geeksforgeeks";

n = len(str1);

  

tree = [[0 for x in range(27)] for y in range(max)];

buildBIT(tree, str1, n);

  

qType1(tree, 4, 'g', str1);

qType2(tree, 1, 4, str1);

qType2(tree, 2, 3, str1);

qType1(tree, 10, 't', str1);

qType2(tree, 10, 11, str1);

  

  
# Этот код предоставлен mits

C #

// C # программа для запросов на подстроку палиндрома
// формирование.

using System;

  

class GFG

{

  

    static int max = 1000;

  

    // Возвращаем частоту символа в

    // i-й префикс.

    static int getFrequency(int [,]tree, int idx, int i)

    {

        int sum = 0;

  

        while (idx > 0)

        {

            sum += tree[idx,i];

            idx -= (idx & -idx);

        }

  

        return sum;

    }

  

    // Обновление BIT

    static void update(int [,]tree, int idx,

                    int val, int i)

    {

        while (idx <= max) 

        {

            tree[idx,i] += val;

            idx += (idx & -idx);

        }

    }

  

    // Запрос на обновление символа в строке.

    static void qType1(int [,]tree, int l, int x, char []str)

    {

        // Добавляем -1 в позицию L

        update(tree, l, -1, str[l - 1] - 97 + 1);

  

        // Обновление персонажа

        str[l - 1] = (char)x;

  

        // Добавляем +1 в позицию R

        update(tree, l, 1, str[l - 1] - 97 + 1);

    }

  

    // Запрос, чтобы найти перестановку символа в диапазоне

    // L ... R может образовывать палиндром

    static void qType2(int [,]tree, int l, int r, char []str)

    {

        int count = 0;

  

        for (int i = 1; i <= 26; i++) 

        {

            // Проверка первого символа строки S.

            if (l == 1) 

            {

                if (getFrequency(tree, r, i) % 2 == 1)

                    count++;

            }

            else

            {

                // Проверка, является ли частота символа четной или нечетной.

                if ((getFrequency(tree, r, i) - getFrequency(tree, l - 1, i)) % 2 == 1)

                    count++;

            }

        }

  

        if (count <= 1)

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

  

    // Создание бинарного дерева индексов всего алфавита

    static void buildBIT(int [,]tree, char []str, int n)

    {

  

        for (int i = 0; i < n; i++)

            update(tree, i + 1, 1, str[i] - 97 + 1);

    }

  

    // Код драйвера

    static void Main()

    {

        char []str = "geeksforgeeks".ToCharArray();

        int n = str.Length;

  

        int[,] tree = new int[max,27];

        buildBIT(tree, str, n);

  

        qType1(tree, 4, 'g', str);

        qType2(tree, 1, 4, str);

        qType2(tree, 2, 3, str);

        qType1(tree, 10, 't', str);

        qType2(tree, 10, 11, str);

    }

}

  
// Этот код предоставлен mits

Выход:

Yes
Yes
No

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Запросы по формированию подстроки палиндрома

0.00 (0%) 0 votes