Tutorialspoint.dev

Queries on substring palindrome formation

Given a string S, and two type of queries.

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| 

Examples:

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".



Substring S[L…R] form a palindrome only if frequencies of all the character in S[L…R] are even, with one except allowed.

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.

Following are two different methods to find frequency of each character in S[L…R]:

Method 1: Use a frequency array to find the frequency of each element in S[L…R].

Below is the implementation of this approach:

C++



// C++ program to Queries on substring palindrome
// formation.
#include<bits/stdc++.h>
using namespace std;
  
// Query type 1: update string position i with
// character x.
void qType1(int l, int x, char str[])
{
    str[l-1] = x;
}
  
// Print "Yes" if range [L..R] can form palindrome,
// else print "No".
void qType2(int l, int r, char str[])
{
    int freq[27] = { 0 };
  
    // Find the frequency of each character in
    // S[L...R].
    for (int i = l-1; i<=r-1; i++)
        freq[str[i] - 'a']++;
  
    // Checking if more than one character have
    // frequency greater than 1.
    int count = 0;
    for (int j = 0; j < 26; j++)
        if (freq[j] % 2)
            count++;
  
    (count<=1)? (cout << "Yes" << endl):
                 (cout << "No" << endl);
}
  
// Driven Program
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

// Java program to Queries on substring
// palindrome formation. 
  
class GFG 
{
  
    // Query type 1: update string  
    // position i with character x. 
    static void qType1(int l, int x, char str[])
    {
        str[l - 1] = (char) x;
    }
  
    // Print "Yes" if range [L..R] can form  
    // palindrome, else print "No". 
    static void qType2(int l, int r, char str[]) 
    {
        int freq[] = new int[27];
  
        // Find the frequency of each  
        // character in S[L...R]. 
        for (int i = l - 1; i <= r - 1; i++) 
        {
            freq[str[i] - 'a']++;
        }
  
        // Checking if more than one character  
        // have frequency greater than 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");
        }
    }
  
    // Driven code 
    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);
    }
  
// This code is contributed by 29AjayKumar

Python3

# Python3 program to Queries on substring 
# palindrome formation.
  
# Query type 1: update str1ing position 
# i with character x.
def qType1(l, x, str1):
    str1[l - 1] = x
  
# Pr"Yes" if range [L..R] can form palindrome,
# else pr"No".
def qType2(l, r, str1):
  
    freq = [0 for i in range(27)] 
  
    # Find the frequency of 
    # each character in S[L...R].
    for i in range(l - 1, r):
        freq[ord(str1[i]) - ord('a')] += 1
  
    # Checking if more than one character 
    # have frequency greater than 1.
    count = 0
    for j in range(26):
        if (freq[j] % 2):
            count += 1
    if count <= 1:
        print("Yes")
    else:
        print("No")
  
# Driver Code
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)
  
# This code is contributed by mohit kumar

C#

// C# program to Queries on substring
// palindrome formation.
using System;
  
class GFG 
{
  
    // Query type 1: update string 
    // position i with character x. 
    static void qType1(int l, int x, char []str)
    {
        str[l - 1] = (char) x;
    }
  
    // Print "Yes" if range [L..R] can form 
    // palindrome, else print "No". 
    static void qType2(int l, int r, char []str) 
    {
        int []freq = new int[27];
  
        // Find the frequency of each 
        // character in S[L...R]. 
        for (int i = l - 1; i <= r - 1; i++) 
        {
            freq[str[i] - 'a']++;
        }
  
        // Checking if more than one character 
        // have frequency greater than 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");
        }
    }
  
    // Driver code 
    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);
    }
}
  
// This code contributed by Rajput-Ji


Output:

Yes
Yes
No

 

Method 2 : Use Binary Indexed Tree
The efficient approach can be maintain 26 Binary Index Tree for each alphabet.
Define a function getFrequency(i,u) which returns the frequency of ‘u’ in the ith prefix. Frequency of character ‘u’ in range L…R can be find by getFrequency(R, u) – getFrequency(L-1, u).
Whenever update(Query 1) comes to change S[i] from character ‘u’ to ‘v’. BIT[u] is updated with -1 at index i and BIT[v] is updated with +1 at index i.

Below is C++ implementation of this approach:

// C++ program to Queries on substring palindrome
// formation.
#include <bits/stdc++.h>
#define max 1000
using namespace std;
  
// Return the frequency of the character in the
// i-th prefix.
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;
}
  
// Updating the BIT
void update(int tree[max][27], int idx, int val, int i)
{
    while (idx <= max)
    {
        tree[idx][i] += val;
        idx += (idx & -idx);
    }
}
  
// Query to update the character in the string.
void qType1(int tree[max][27], int l, int x, char str[])
{
    // Adding -1 at L position
    update(tree, l, -1, str[l-1]-97+1);
  
    // Updating the character
    str[l-1] = x;
  
    // Adding +1 at R position
    update(tree, l, 1, str[l-1]-97+1);
}
  
// Query to find if rearrangement of charcater in range
// L...R can form palindrome
void qType2(int tree[max][27], int l, int r, char str[])
{
    int count = 0;
  
    for (int i = 1; i <= 26; i++)
    {
        // Checking on the first charcter of the string S.
        if (l == 1)
        {
            if (getFrequency(tree, r, i)%2 == 1)
                count++;
        }
        else
        {
            // Checking if frequency of character is even or odd.
            if ((getFrequency(tree, r, i) -
                 getFrequency(tree, l-1, i))%2 == 1)
                count++;
        }
    }
  
    (count<=1)?(cout << "Yes" << endl):(cout << "No" << endl);
}
  
// Creating the Binary Index Tree of all aphabet
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);
}
  
// Driven Program
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;
}

Output:

Yes
Yes
No

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter