Check for Palindrome after every character replacement Query
Given a string str and Q queries. Each query contains a pair of integers (i1, i2) and a character ‘ch’. We need to replace characters at indexes i1 and i2 with new character ‘ch’ and then tell if string str is palindrome or not. (0 <= i1, i2 < string_length)
Examples:
Input : str = "Beginner" Q = 2 query 1: i1 = 3 ,i2 = 0, ch = 'e' query 2: i1 = 0 ,i2 = 2, ch = 's' Output : query 1: "NO" query 2: "NO" Explanation : In query 1 : i1 = 3 , i2 = 0 ch = 'e' After replacing char at index i1, i2 str[3] = 'e', str[0] = 'e' string become "eeees" which is not palindrome so output "NO" In query 2 : i1 = 0 i2 = 2 ch = 's' After replacing char at index i1 , i2 str[0] = 's', str[2] = 's' string become "sesks" which is palindrome so output "NO" Input : str = "jasonamat" Q = 3 query 1: i1 = 3, i2 = 8 ch = 'j' query 2: i1 = 2, i2 = 6 ch = 'n' query 3: i1 = 3, i2 = 7 ch = 'a' Output : query 1: "NO" query 2: "NO" query 3: "YES"
A Simple solution is that for each query , we replace character at indexes (i1 & i2) with a new character ‘ch’ and then check if string is palindrome or not.
Below is implementation of above idea
C++
// C++ program to find if string becomes palindrome // after every query. #include<bits/stdc++.h> using namespace std; // Function to check if string is Palindrome or Not bool isPalindrome(string &str) { int n = str.size(); for ( int i = 0; i < n/2 ; i++) if (str[i] != str[n-1-i]) return false ; return true ; } // Takes two inputs for Q queries. For every query, it // prints Yes if string becomes palindrome and No if not. void Query(string &str, int Q, vector<pair<pair< int , int >, char >> &query) { int i1, i2; char ch; // Process all queries one by one for ( int q = 0 ; q < Q ; q++ ) { i1 = query[q].first.first; i2 = query[q].first.second; ch = query[q].second; str[i1] = str[i2] = ch; // check string is palindrome or not (isPalindrome(str)== true ) ? cout << "YES" << endl : cout << "NO" << endl; } } // Driver program int main() { string str = "Beginner" ; int Q = 2; vector<pair<pair< int , int >, char >> query = {{{3, 0}, 'e' }, {{0, 2}, 's' }}; Query(str, Q, query); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { // Java program to find if string becomes palindrome // after every query. // Function to check if string is Palindrome or Not static boolean IsPalindrome(String str) { int n = str.length(); for ( int i = 0 ; i < n/ 2 ; i++) if (str.charAt(i) != str.charAt(n- 1 -i)) return false ; return true ; } // Takes two inputs for Q queries. For every query, it // prints Yes if string becomes palindrome and No if not. static void Query(String str, int Q) { int i1, i2; char ch; Scanner sc = new Scanner(System.in); for ( int q = 1 ; q <= Q ; q++ ) { i1 = sc.nextInt(); i2 = sc.nextInt(); ch = sc.next().charAt( 0 ); // query 1: i1 = 3 ,i2 = 0, ch = 'e' // query 2: i1 = 0 ,i2 = 2 , ch = 's' // replace character at index i1 & i2 with new 'ch' str = str.substring( 0 ,Math.min(i1,i2)) + ch + str.substring(Math.min(i1+ 1 ,i2+ 1 ), Math.max(i2+ 1 ,i1+ 1 )) + ch + str.substring(Math.max(i2+ 1 ,i1+ 1 )); // check string is palindrome or not if (IsPalindrome(str)== true ) System.out.println( "YES" ); else System.out.println( "NO" ); } sc.close(); } // Driver Code public static void main(String args[]) { String str = "Beginner" ; int Q = 2 ; Query(str, Q); } } // This Solution is contributed by shinjanpatra. |
Python3
# Python3 program to find if # string becomes palindrome # after every query. # Function to check if string # is Palindrome or Not def isPalindrome(string: list ) - > bool : n = len (string) for i in range (n / / 2 ): if string[i] ! = string[n - 1 - i]: return False return True # Takes two inputs for Q queries. # For every query, it prints Yes # if string becomes palindrome # and No if not. def Query(string: list , Q: int ) - > None : # Process all queries one by one for i in range (Q): # To get space separated # input from user inp = list ( input ().split()) # parsing user inputs as integers # and strings/char i1 = int (inp[ 0 ]) i2 = int (inp[ 1 ]) ch = inp[ 2 ] # query 1: i1 = 3 ,i2 = 0, ch = 'e' # query 2: i1 = 0 ,i2 = 2 , ch = 's' # replace character at index # i1 & i2 with new 'ch' string[i1] = string[i2] = ch # check string is palindrome or not if isPalindrome(string): print ( "Yes" ) else : print ( "No" ) # Driver Code if __name__ = = "__main__" : string = list ( "Beginner" ) Q = 2 Query(string, Q) # This code is contributed by # sanjeev2552 |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class Program { // Function to check if string is Palindrome or Not public static bool IsPalindrome( ref string str) { int n = str.Length; for ( int i = 0; i < n / 2; i++) { if (str[i] != str[n - 1 - i]) { return false ; } } return true ; } // Takes two inputs for Q queries. For every query, it // prints Yes if string becomes palindrome and No if not. public static void Query( ref string str, int Q, List<Tuple<Tuple< int , int >, char >> query) { int i1, i2; char ch; // Process all queries one by one for ( int q = 0; q < Q; q++) { i1 = query[q].Item1.Item1; i2 = query[q].Item1.Item2; ch = query[q].Item2; str = str.Remove(i1, 1).Insert(i1, ch.ToString()); str = str.Remove(i2, 1).Insert(i2, ch.ToString()); // check string is palindrome or not Console.WriteLine(IsPalindrome( ref str) == true ? "YES" : "NO" ); } } // Driver program public static void Main() { string str = "Beginner" ; int Q = 2; List<Tuple<Tuple< int , int >, char >> query = new List<Tuple<Tuple< int , int >, char >>() { Tuple.Create(Tuple.Create(3, 0), 'e' ), Tuple.Create(Tuple.Create(0, 2), 's' ) }; Query( ref str, Q, query); } } // This code is contributed prince |
Javascript
// JavaScript program to find if // string becomes palindrome // after every query. // Function to check if string // is Palindrome or Not function isPalindrome(string) { let n = string.length; for (let i = 0; i < n / 2; i++) { if (string[i] !== string[n - 1 - i]) { return false ; } } return true ; } // Takes two inputs for Q queries. // For every query, it prints Yes // if string becomes palindrome // and No if not. function Query(string, Q) { // Process all queries one by one for (let i = 0; i < Q; i++) { // To get space separated // input from user let inp = prompt().split( ' ' ); // parsing user inputs as integers // and strings/char let i1 = parseInt(inp[0]); let i2 = parseInt(inp[1]); let ch = inp[2]; // query 1: i1 = 3 ,i2 = 0, ch = 'e' // query 2: i1 = 0 ,i2 = 2 , ch = 's' // replace character at index // i1 & i2 with new 'ch' string[i1] = string[i2] = ch; // check string is palindrome or not if (isPalindrome(string)) { console.log( "Yes" ); } else { console.log( "No" ); } } } // Driver Code let string = [ 'g' , 'e' , 'e' , 'k' , 's' ]; let Q = 2; Query(string, Q); // This code is contributed by adityashatmfh |
NO YES
Time complexity O(Q*n) (n is length of string )
An efficient solution is to use hashing. We create an empty hash set that stores indexes that are unequal in palindrome (Note: ” we have to store indexes only first half of string that are unequal “).
Given string "str" and length 'n'. Create an empty set S and store unequal indexes in first half. Do following for each query : 1. First replace character at indexes i1 & i2 with new char "ch" 2. If i1 and/or i2 are/is greater than n/2 then convert into first half index(es) 3. In this step we make sure that S contains maintains unequal indexes of first half. a) If str[i1] == str [n - 1 - i1] means i1 becomes equal after replacement, remove it from S (if present) Else add i1 to S b) Repeat step a) for i2 (replace i1 with i2) 4. If S is empty then string is palindrome else NOT
Below is C++ implementation of above idea
CPP
// C++/c program check if given string is palindrome // or not after every query #include <bits/stdc++.h> using namespace std; // This function makes sure that set S contains // unequal characters from first half. This is called // for every character. void addRemoveUnequal(string& str, int index, int n, unordered_set< int >& S) { // If character becomes equal after query if (str[index] == str[n - 1 - index]) { // Remove the current index from set if it // is present auto it = S.find(index); if (it != S.end()) S.erase(it); } // If not equal after query, insert it into set else S.insert(index); } // Takes two inputs for Q queries. For every query, it // prints Yes if string becomes palindrome and No if not. void Query(string& str, int Q, vector<pair<pair< int , int >, char >> &query) { int n = str.length(); // create an empty set that store indexes of // unequal location in palindrome unordered_set< int > S; // we store indexes that are unequal in palindrome // traverse only first half of string for ( int i = 0; i < n / 2; i++) if (str[i] != str[n - 1 - i]) S.insert(i); // traversal the query for ( int q = 0; q < Q; q++) { int i1, i2; char ch; i1 = query[q].first.first; i2 = query[q].first.second; ch = query[q].second; // Replace characters at indexes i1 & i2 with // new char 'ch' str[i1] = str[i2] = ch; // If i1 and/or i2 greater than n/2 // then convert into first half index if (i1 > n / 2) i1 = n - 1 - i1; if (i2 > n / 2) i2 = n - 1 - i2; // call addRemoveUnequal function to insert and // remove unequal indexes addRemoveUnequal(str, i1, n, S); addRemoveUnequal(str, i2, n, S); // if set is not empty then string is not palindrome S.empty() ? cout << "YES\n" : cout << "NO\n" ; } } // Driver program int main() { string str = "Beginner" ; int Q = 2; vector<pair<pair< int , int >, char > > query = { { { 3, 0 }, 'e' }, { { 0, 2 }, 's' } }; Query(str, Q, query); return 0; } |
Java
import java.util.*; class Main { // This function makes sure that set S contains // unequal characters from first half. This is called // for every character. static void addRemoveUnequal(StringBuilder str, int index, int n, HashSet<Integer> S) { // If character becomes equal after query if (str.charAt(index) == str.charAt(n - 1 - index)) { // Remove the current index from set if it // is present if (S.contains(index)) S.remove(index); } // If not equal after query, insert it into set else { S.add(index); } } // Takes two inputs for Q queries. For every query, it // prints Yes if string becomes palindrome and No if not. static void Query(StringBuilder str, int Q, ArrayList<Pair<Pair<Integer, Integer>, Character>> query) { int n = str.length(); // create an empty set that store indexes of // unequal location in palindrome HashSet<Integer> S = new HashSet<>(); // we store indexes that are unequal in palindrome // traverse only first half of string for ( int i = 0 ; i < n / 2 ; i++) if (str.charAt(i) != str.charAt(n - 1 - i)) S.add(i); // traversal the query for ( int q = 0 ; q < Q; q++) { int i1, i2; char ch; i1 = query.get(q).first.first; i2 = query.get(q).first.second; ch = query.get(q).second; // Replace characters at indexes i1 & i2 with // new char 'ch' str.setCharAt(i1, ch); str.setCharAt(i2, ch); // If i1 and/or i2 greater than n/2 // then convert into first half index if (i1 > n / 2 ) i1 = n - 1 - i1; if (i2 > n / 2 ) i2 = n - 1 - i2; // call addRemoveUnequal function to insert and // remove unequal indexes addRemoveUnequal(str, i1, n, S); addRemoveUnequal(str, i2, n, S); // if set is not empty then string is not palindrome System.out.println(S.isEmpty() ? "YES" : "NO" ); } } // Driver program public static void main(String[] args) { StringBuilder str = new StringBuilder( "Beginner" ); int Q = 2 ; ArrayList<Pair<Pair<Integer, Integer>, Character>> query = new ArrayList<>(); query.add( new Pair<>( new Pair<>( 3 , 0 ), 'e' )); query.add( new Pair<>( new Pair<>( 0 , 2 ), 's' )); Query(str, Q, query); } } // class for pair class Pair<U, V> { public final U first; public final V second; public Pair(U first, V second) { this .first = first; this .second = second; } } |
Python3
# Python program to check if a given string is a palindrome or not after every query # This function makes sure that set S contains # unequal characters from the first half. This is called # for every character. def addRemoveUnequal(s, index, n, S): # If character becomes equal after query if s[index] = = s[n - 1 - index]: # Remove the current index from set if it # is present if index in S: S.remove(index) # If not equal after query, insert it into set else : S.add(index) # Takes two inputs for Q queries. For every query, it # prints Yes if string becomes palindrome and No if not. def Query(s, Q, query): n = len (s) # create an empty set that stores indexes of # unequal location in palindrome S = set () # we store indexes that are unequal in palindrome # traverse only first half of string for i in range (n / / 2 ): if s[i] ! = s[n - 1 - i]: S.add(i) # traverse the query for q in range (Q): i1, i2 = query[q][ 0 ] ch = query[q][ 1 ] # Replace characters at indexes i1 & i2 with # new char 'ch' s = s[:i1] + ch + s[i1 + 1 :] s = s[:i2] + ch + s[i2 + 1 :] # If i1 and/or i2 greater than n/2 # then convert into first half index if i1 > n / / 2 : i1 = n - 1 - i1 if i2 > n / / 2 : i2 = n - 1 - i2 # call addRemoveUnequal function to insert and # remove unequal indexes addRemoveUnequal(s, i1, n, S) addRemoveUnequal(s, i2, n, S) # if set is not empty then string is not palindrome print ( "NO" if S else "YES" ) # Driver program if __name__ = = '__main__' : s = "Beginner" Q = 2 query = [(( 3 , 0 ), 'e' ), (( 0 , 2 ), 's' )] Query(s, Q, query) |
C#
using System; using System.Collections.Generic; using System.Text; class Program { // This function makes sure that set S contains // unequal characters from first half. This is called // for every character. static void AddRemoveUnequal(StringBuilder str, int index, int n, HashSet< int > S) { // If character becomes equal after query if (str[index] == str[n - 1 - index]) { // Remove the current index from set if it // is present if (S.Contains(index)) { S.Remove(index); } } // If not equal after query, insert it into set else { S.Add(index); } } // Takes two inputs for Q queries. For every query, it // prints Yes if string becomes palindrome and No if not. static void Query(StringBuilder str, int Q, List<Tuple<Tuple< int , int >, char >> query) { int n = str.Length; // create an empty set that store indexes of // unequal location in palindrome HashSet< int > S = new HashSet< int >(); // we store indexes that are unequal in palindrome // traverse only first half of string for ( int i = 0; i < n / 2; i++) { if (str[i] != str[n - 1 - i]) { S.Add(i); } } // traversal the query for ( int q = 0; q < Q; q++) { int i1, i2; char ch; i1 = query[q].Item1.Item1; i2 = query[q].Item1.Item2; ch = query[q].Item2; // Replace characters at indexes i1 & i2 with // new char 'ch' str[i1] = ch; str[i2] = ch; // If i1 and/or i2 greater than n/2 // then convert into first half index if (i1 > n / 2) { i1 = n - 1 - i1; } if (i2 > n / 2) { i2 = n - 1 - i2; } // call addRemoveUnequal function to insert and // remove unequal indexes AddRemoveUnequal(str, i1, n, S); AddRemoveUnequal(str, i2, n, S); // if set is not empty then string is not palindrome Console.WriteLine(S.Count == 0 ? "YES" : "NO" ); } } // Driver program static void Main( string [] args) { StringBuilder str = new StringBuilder( "Beginner" ); int Q = 2; List<Tuple<Tuple< int , int >, char >> query = new List<Tuple<Tuple< int , int >, char >>(); query.Add( new Tuple<Tuple< int , int >, char >( new Tuple< int , int >(3, 0), 'e' )); query.Add( new Tuple<Tuple< int , int >, char >( new Tuple< int , int >(0, 2), 's' )); Query(str, Q, query); } } |
Javascript
// This function makes sure that set S contains // unequal characters from the first half. This is called // for every character. function addRemoveUnequal(s, index, n, S) { // If character becomes equal after query if (s[index] === s[n - 1 - index]) { // Remove the current index from set if it // is present if (S.has(index)) { S. delete (index); } } // If not equal after query, insert it into set else { S.add(index); } } // Takes two inputs for Q queries. For every query, it // prints Yes if string becomes palindrome and No if not. function Query(s, Q, query) { let n = s.length; // create an empty set that stores indexes of // unequal location in palindrome let S = new Set(); // we store indexes that are unequal in palindrome // traverse only first half of string for (let i = 0; i < n / 2; i++) { if (s[i] !== s[n - 1 - i]) { S.add(i); } } // traverse the query for (let q = 0; q < Q; q++) { let [i1, i2] = query[q][0]; let ch = query[q][1]; // Replace characters at indexes i1 & i2 with // new char 'ch' s = s.substring(0, i1) + ch + s.substring(i1 + 1); s = s.substring(0, i2) + ch + s.substring(i2 + 1); // If i1 and/or i2 greater than n/2 // then convert into first half index if (i1 > n / 2) { i1 = n - 1 - i1; } if (i2 > n / 2) { i2 = n - 1 - i2; } // call addRemoveUnequal function to insert and // remove unequal indexes addRemoveUnequal(s, i1, n, S); addRemoveUnequal(s, i2, n, S); // if set is not empty then string is not palindrome console.log(S.size === 0 ? "YES" : "NO" ); } } // Driver program let s = "Beginner" ; let Q = 2; let query = [[[3, 0], 'e' ], [[0, 2], 's' ]]; Query(s, Q, query); |
NO YES
Time Complexity: O(Q + n) under the assumption that set insert, delete and find operations take O(1) time.
Contact Us