Check for Palindrome after every character replacement Query

Difficulty Level Hard
Frequently asked in Amazon Facebook Flipkart Google Netflix
Hash StringViews 1904

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.

Example

Check for Palindrome after every character replacement Query

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

  1. Declare a Set.
  2. Store all the unequal indexes for the first half in a Set.
  3. Change the characters with the given character values at the given index (i1 and i2).
    1. Check if i1 > n/2 then do i1=n-1-i1 and i2 > n/2, if true then do i2=n-1-i2 respectively.
    2. 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.
      1. Else add i1 to Set.
    3. Repeat this process for i2 as well.
  4. Repeat from step 3 till the total number of queries given.
  5. 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.

Translate »