Home » Technical Interview Questions » Hashing Interview Questions » Check for Palindrome after every character replacement Query

Check for Palindrome after every character replacement Query


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.
READ  Numbers with prime frequencies greater than or equal to k

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.

READ  Find all pairs (a, b) in an array such that a % b = k

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.

READ  Find pairs with given sum such that elements of pair are in different rows

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup