The problem “Check for Palindrome after every character replacement Query” states that suppose you are given a String and no. of Queries, each query has two integer input values as i1 and i2 and one character input called ‘ch’. The problem statement asks to change the values at i1 and i2 indices with the given character ‘ch’ and determine whether it is a palindrome or not.
Note: 0 < is less than or equal to i1 and i2 is less than or equal to the length of the string.
Table of Contents
Example
String: india, Query=2. Query 1: i1 = 0, i2 = 4, ch = i Query 2: i1 = 1, i2 = 3, ch = n
Query 1: No Query 2: Yes
Explanation
Query 1: india becomes after replacement indii
Query 2: indii becomes after replacement indni
String: english, Query=3. Query 1: i1 = 0, i2 = 6, ch = e Query 2: i1 = 1, i2 = 5, ch = s Query 3: i1 = 2, i2 = 4, ch = i
Query 1: No Query 2: No Query 3: Yes
Explanation
Query 1: english becomes after replacement englise
Query 2: englise becomes after replacement esglise
Query 3: esglise becomes after replacement esilise
Algorithm
- Declare a Set.
- Store all the unequal indexes for the first half in a Set.
- Change the characters with the given character values at the given index (i1 and i2).
- Check if i1 > n/2 then do i1=n-1-i1 and i2 > n/2, if true then do i2=n-1-i2 respectively.
- Now check if after replacement str[i1] == str[n-1-i1], if it is found to be true, then check if i1 is present in a Set or not, if present then removes it.
- Else add i1 to Set.
- Repeat this process for i2 as well.
- Repeat from step 3 till the total number of queries given.
- If Set if empty then it is palindrome else it is not.
Explanation
We are given a String and some number of Queries, which contains some integer and character input values in it, we need to change or replace the characters with the given character and at certain indices which are given as i1 and i2 and then after we need to determine if string formed is palindrome or not after each query performed. The idea is to use hashing. We are going to use Set to solve this problem. We are going to make separate function one function is to take queries and another function is to check palindrome. Basically, that function works in a bit by bit fashion. Because of each call we make to that function. It performs operations on Set and in return when we check whether Set is empty or not. It is empty it means the string is a palindrome, else it is not.
Let us consider an example:
Example
String: india, Query=2, means it will take inputs of i1, i2 and ch 2 times.
We need to store the unequal indexes of the first half of string
So after traversing the whole string, we will have Set like this,
Set: [0, 1]
For 1st query, i1=0, i2=4, ch=i, means string “india” becomes “indii”.
i1 remains i1 as 0, i2 becomes 0, first, i1 will pass and check if str[i1] == str[n-1-i1], it is true, then it will check for i1 is present in a set, it is also present, so it will remove i1 means 0 from the set.
Then i2 is also 0 so nothing gonna happen.
For 2nd query, i1=1, i2=3, ch=n, means string “indii” becomes “indni ”.
i1 remains i1 as 1, i2 becomes 1, first, i1 will pass and check if str[i1] == str[n-1-i1], it is true, then it will check for i1 is present in a set, it is also present, so it will remove i1 means 1 from the set. Then after all the queries performed it will check if Set is empty and now it is empty and it will print yes because in a set there were two values 0 and 1 and we removed both of these.
C++ code to Check for Palindrome after every character replacement Query
#include<unordered_set>
#include<iostream>
using namespace std;
void checkPalindrome(string &str, int index, int n,unordered_set<int> &SET)
{
if (str[index] == str[n-1-index])
{
if (SET.find(index) != SET.end())
SET.erase(SET.find(index)) ;
}
else
SET.insert(index);
}
void getQuery(string &str, int query)
{
int n = str.length();
unordered_set<int> SET;
for (int i=0; i<n/2; i++)
if (str[i] != str[n-1-i])
SET.insert(i);
for (int QueryNo=1; QueryNo<=query; QueryNo++)
{
cout << "Values for query " << QueryNo <<endl;
int i1, i2;
char ch;
cout << "Enter i1 ";
cin >> i1;
cout << "Enter i2 ";
cin >> i2;
cout << "Enter ch ";
cin >> ch;
str[i1] = str [i2] = ch;
if (i1 > n/2)
i1 = n- 1 -i1;
if (i2 > n/2)
i2 = n -1 - i2;
checkPalindrome(str, i1, n, SET );
checkPalindrome(str, i2, n, SET );
cout << "Output for query " << QueryNo << " => ";
SET.empty()? cout << "YES"<<endl<<endl : cout << "NO"<<endl<<endl;
}
}
int main()
{
string str = "india";
int query = 2 ;
getQuery(str, query);
return 0;
}
Values for query 1 Enter i1 0 Enter i2 4 Enter ch i Output for query 1 => NO Values for query 2 Enter i1 1 Enter i2 3 Enter ch n Output for query 2 => YES
Java code to Check for Palindrome after every character replacement Query
import java.util.Scanner;
import java.util.HashSet;
class SearchPalindrome
{
private static Scanner sc=new Scanner(System.in);
public static void checkPalindrome(String str, int i, int n,HashSet<Integer> SET)
{
if (str.charAt(i) == str.charAt(n-1-i))
{
if (SET.contains(i))
SET.remove(i) ;
}
else
SET.add(i);
}
public static void Query(String str, int Q)
{
int n = str.length();
HashSet<Integer> SET=new HashSet<>();
for (int i=0; i<n/2; i++)
if (str.charAt(i) != str.charAt(n-1-i))
SET.add(i);
for (int query=1; query<=Q; query++)
{
System.out.println("Values for query " + query);
int i1, i2;
char ch;
System.out.print("Enter i1 " );
i1=sc.nextInt();
System.out.print("Enter i2 ");
i2=sc.nextInt();
System.out.print("Enter ch ");
ch=sc.next().charAt(0);
char[] strChars = str.toCharArray();
strChars[i1] = ch;
strChars[i2] = ch;
str = String.valueOf(strChars);
if (i1 > n/2)
i1 = n- 1 -i1;
if (i2 > n/2)
i2 = n -1 - i2;
checkPalindrome(str, i1, n, SET );
checkPalindrome(str, i2, n, SET );
System.out.print("Output for query " + query + " => ");
if(SET.isEmpty())
System.out.println("YES\n\n");
else
System.out.println("NO\n");
}
}
public static void main(String args[])
{
String str = "india";
int query = 2 ;
Query(str, query);
}
}
Values for query 1 Enter i1 0 Enter i2 4 Enter ch i Output for query 1 => NO Values for query 2 Enter i1 1 Enter i2 3 Enter ch n Output for query 2 => YES
Complexity Analysis
Time Complexity
O(Q+N) where “Q” is the number of queries and “N” is the length of the string. Since first we run a loop until the half-length of string and add all unequal indices to map and then compute the queries which individually take O(1) time. The time complexity becomes linear.
Space Complexity
O(N), because we are adding the elements of the input sequence into the map. And in the worst case, we can have all unequal characters at all of the indices. This will cost us an O(N) space.