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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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 = { 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``; ` ` `  `        ``// 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 ` `#define max 1000 ` `using` `namespace` `std; ` ` `  `// Return the frequency of the character in the ` `// i-th prefix. ` `int` `getFrequency(``int` `tree[max], ``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], ``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], ``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], ``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], ``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]; ` `    ``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

code

load comments