String Comparison and Manipulation Queries with Blocking and Swapping
Given Two strings S1 and S2 of equal length N, consisting of lowercase letters. There are also given integer T and Q queries. Each query can be one of three types, for queries of the first and second types, the specified positions and characters are not blocked. The task for this problem is to print the answer for query type 3.
- Type 1: {1, pos} Block characters at position pos in both strings for the next T queries (including the current query).
- Type 2: {2, string1, pos1, string2, pos2} Swap two unblocked characters from the same or different strings. Here string1 and string2 can be S1 or S2.
- Type 3: {3} Print “YES” if both strings are equal after ignoring blocked characters, else print “NO“.
Examples:
Input: S1 = “cool”, S2 = “club”, T = 2, Q[][] = {{2, 1, 2, 2, 3}, {2, 2, 2, 2, 4}, {1, 2}, {3}, {3}}
Output: YES NO
Explanation:
- Query – {type = 2, string1 = 1, pos1 = 2, string2 = 2, pos2 = 3}: This query is of type 2 swap S1’s 2nd character with S2’s 3’rd character. S1 and S2 becomes (S1, S2) = (cuol, clob)
- Query – {type = 2, string1 = 2, pos1 = 2, string2 = 2, pos2 = 4}: This query if of type 2 swap S2’s 2nd character with S2’s 4’th character. S1 and S2 becomes (S1, S2) = (cuol, cbol)
- Query – {type = 1, pos = 2}: This query is of type 1 block character 2 for T = 2 queries.
- Query – {type = 3}: This query is of type 3, S1 = “cuol” and S2 = “cbol” are equal since character 2 is blocked and all other characters are equal. So print “YES”.
- Query – {type = 3}: This query is of type 3, S1 = “cuol” and S2 = “cbol” are not equal since character 2 is different. So print “NO”.
Input: S1 = “aaab”, S2 = “bbba”, T = 1, Q[][] = {{2, 1, 3, 2, 4}, {3} , {2, 1, 2, 2, 2}, {3}, {2, 1, 4, 2, 1}, {3}, {2, 1, 2, 2, 1}, {3}}
Output: NO NO NO NO
Approach: To solve the problem follow the below idea:
- Define a variable that will be tracking number of positions in string S1 and S2 that has same character ( i such that S1[i] == S2[i] ) let’s call it curScore. If this is equal to size of the string that is N then answer for that query will be YES else NO. This is how query of type 3 will be handled.
- To handle query of type 1 there will be need of queue data structure. If any position we are blocking and it has characters that are not equal at that position then curScore will be increased by 1 because from now on we will count this position as equal and after T queries including current query we will unblock this position that is this position will be unequal again so to subtract 1 from curScore. we will push element in queue that is query at which we will unblock.(subtract 1 that was added initially from curScore).
- To handle second query that has pos1 and pos2 that is going to get swapped before swapping if any of these position has equal characters (S1[pos1] == S2[pos1] or S1[pos2] == S2[pos2]) then subtract 1 from curScore for each because after swapping they might change to unequal characters. After swapping now again check if any of these positions has equal characters (S1[pos1 == S2[pos1] or S1[pos2] == S2[pos2]) then add 1 to curScore for each position.
Steps to solve the question:
- Initializes curScore to 0, which keeps track of the number of equal characters between S1 and S2.
- It then iterates through the strings, comparing characters at corresponding positions and incrementing curScore when characters match.
- Define queue data structure q to keep track of blocked positions.
- It iterates through each query in the vector Q and processes each query according to its type.
- Query Type 1: Q[i][0] == 1
- This query type involves blocking a character at a specific position.
- It checks if the character at position pos in both S1 and S2 is different. If they are different, it increments the curScore variable, which keeps track of the number of characters that are equal in both strings.
- The position i + T will be unblocked in T queries later. This information is stored in a queue q.
- Query Type 2: Q[i][0] == 2
- This query type involves swapping characters between the two strings or within a single string.
- It checks if the characters at pos1 and pos2 in both S1 and S2 are the same before swapping. If they are the same, it decrements the curScore variable for each position.
- Depending on the values of string1 and string2, the code swaps characters between S1 and S2, or within S1 or S2.
- After swapping, it checks if the characters at pos1 and pos2 in both strings are now equal. If they are, it increments the curScore variable for each position.
- Query Type 3: Q[i][0] == 3
- This query type involves checking whether the curScore is equal to N, which means all characters in S1 and S2 are equal.
- If curScore equals N, it prints “YES”; otherwise, it prints “NO”.
- Query Type 1: Q[i][0] == 1
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to answer following three type // of queries void answerQueries(string S1, string S2, int N, int T, vector<vector< int > >& Q) { // current score of the string indicates // the number of characters that are equal // currently int curScore = 0; // iterating over string to find score for ( int i = 0; i < N; i++) { if (S1[i] == S2[i]) curScore++; } // queue for tracking blocked positions queue< int > q; // iterating for all queries for ( int i = 0; i < Q.size(); i++) { // characters unblocking if (!q.empty() and q.front() == i) { int idx = i - T; q.pop(); if (S1[idx] != S2[idx]) curScore--; } // type of query int type = Q[i][0]; if (type == 1) { // position of element which will be blocked int pos = Q[i][1]; // the position we are blocking if it is not // equal then increase the currentScore if (S1[pos - 1] != S2[pos - 1]) curScore++; // inserting the position of query when blocked // characters will be unblocked at given index q.push(i + T); } else if (type == 2) { // string1 will be either S1(1) or S2(2) and the // position pos1 which we have to swap with // string2's either S1(1) or S2(2) and the // position pos2 int string1 = Q[i][1], pos1 = Q[i][2], string2 = Q[i][3], pos2 = Q[i][4]; // if those positions are equal then subtract 1 // from curScore for each position since we are // going to swap them if (S1[pos1 - 1] == S2[pos1 - 1]) curScore--; if (pos1 != pos2 and S1[pos2 - 1] == S2[pos2 - 1]) curScore--; // if character from S1 is swapped with // character from S1 only if (string1 == 1 and string2 == 1) swap(S1[pos1 - 1], S1[pos2 - 1]); // if character from S1 is swapped with // character from S2 else if (string1 == 1 and string2 == 2) swap(S1[pos1 - 1], S2[pos2 - 1]); // if character from S2 is swapped with // character from S1 else if (string1 == 2 and string2 == 1) swap(S2[pos1 - 1], S1[pos2 - 1]); // if character from S2 is swapped with // character from S2 else swap(S2[pos1 - 1], S2[pos2 - 1]); // if those positions are equal then add 1 in // curScore for each position if (S1[pos1 - 1] == S2[pos1 - 1]) curScore++; if (pos1 != pos2 and S1[pos2 - 1] == S2[pos2 - 1]) curScore++; } else { // if current score is equal to N then print YES // else print NO if (curScore == N) cout << "YES" << " "; else cout << "NO" << " "; } } cout << endl; } // Driver Code int32_t main() { // Input 1 string S1 = "cool", S2 = "club"; vector<vector< int > > Q = { { 2, 1, 2, 2, 3 }, { 2, 2, 2, 2, 4 }, { 1, 2 }, { 3 }, { 3 } }; int T = 2, N = S1.size(); // Function Call answerQueries(S1, S2, N, T, Q); // Input 2 string S11 = "aaab", S21 = "bbba"; vector<vector< int > > Q1 = { { 2, 1, 3, 2, 4 }, { 3 }, { 2, 1, 2, 2, 2 }, { 3 }, { 2, 1, 4, 2, 1 }, { 3 }, { 2, 1, 2, 2, 1 }, { 3 } }; int T1 = 2, N1 = S11.size(); // Function Call answerQueries(S11, S21, N1, T1, Q1); return 0; } |
Java
import java.util.ArrayDeque; import java.util.Deque; public class QueryAnswer { // Function to answer following three types of queries public static void answerQueries(String S1, String S2, int N, int T, int [][] Q) { // current score of the string indicates the number of characters that are equal currently int curScore = 0 ; // iterating over the string to find the score for ( int i = 0 ; i < N; i++) { if (S1.charAt(i) == S2.charAt(i)) { curScore += 1 ; } } // queue for tracking blocked positions Deque<Integer> q = new ArrayDeque<>(); // iterating for all queries for ( int i = 0 ; i < Q.length; i++) { // characters unblocking if (!q.isEmpty() && q.peek() == i) { int idx = i - T; q.poll(); if (S1.charAt(idx) != S2.charAt(idx)) { curScore -= 1 ; } } // type of query int type = Q[i][ 0 ]; if (type == 1 ) { // position of the element which will be blocked int pos = Q[i][ 1 ]; // the position we are blocking, if it is not equal then increase the current score if (S1.charAt(pos - 1 ) != S2.charAt(pos - 1 )) { curScore += 1 ; } // inserting the position of the query when blocked characters // will be unblocked at the given index q.offer(i + T); } else if (type == 2 ) { // string1 will be either S1(1) or S2(2) and the position // pos1 which we have to swap with // string2's either S1(1) or S2(2) and the position pos2 int string1 = Q[i][ 1 ]; int pos1 = Q[i][ 2 ]; int string2 = Q[i][ 3 ]; int pos2 = Q[i][ 4 ]; // if those positions are equal then subtract 1 from curScore for each position // since we are going to swap them if (S1.charAt(pos1 - 1 ) == S2.charAt(pos1 - 1 )) { curScore -= 1 ; } if (pos1 != pos2 && S1.charAt(pos2 - 1 ) == S2.charAt(pos2 - 1 )) { curScore -= 1 ; } // if character from S1 is swapped with character from S1 only if (string1 == 1 && string2 == 1 ) { char [] s1Array = S1.toCharArray(); s1Array[pos1 - 1 ] = S1.charAt(pos2 - 1 ); s1Array[pos2 - 1 ] = S1.charAt(pos1 - 1 ); S1 = new String(s1Array); // if character from S1 is swapped with character from S2 } else if (string1 == 1 && string2 == 2 ) { char [] s1Array = S1.toCharArray(); char [] s2Array = S2.toCharArray(); s1Array[pos1 - 1 ] = S2.charAt(pos2 - 1 ); s2Array[pos2 - 1 ] = S1.charAt(pos1 - 1 ); S1 = new String(s1Array); S2 = new String(s2Array); // if character from S2 is swapped with character from S1 } else if (string1 == 2 && string2 == 1 ) { char [] s1Array = S1.toCharArray(); char [] s2Array = S2.toCharArray(); s2Array[pos1 - 1 ] = S1.charAt(pos2 - 1 ); s1Array[pos2 - 1 ] = S2.charAt(pos1 - 1 ); S1 = new String(s1Array); S2 = new String(s2Array); // if character from S2 is swapped with character from S2 } else { char [] s2Array = S2.toCharArray(); s2Array[pos1 - 1 ] = S2.charAt(pos2 - 1 ); s2Array[pos2 - 1 ] = S2.charAt(pos1 - 1 ); S2 = new String(s2Array); } // if those positions are equal then add 1 to curScore for each position if (S1.charAt(pos1 - 1 ) == S2.charAt(pos1 - 1 )) { curScore += 1 ; } if (pos1 != pos2 && S1.charAt(pos2 - 1 ) == S2.charAt(pos2 - 1 )) { curScore += 1 ; } } else { // if the current score is equal to N, then print YES, else print NO if (curScore == N) { System.out.print( "YES " ); } else { System.out.print( "NO " ); } } } System.out.println(); } // Driver Code public static void main(String[] args) { // Input 1 String S1 = "cool" ; String S2 = "club" ; int [][] Q = {{ 2 , 1 , 2 , 2 , 3 }, { 2 , 2 , 2 , 2 , 4 }, { 1 , 2 }, { 3 }, { 3 }}; int T = 2 ; int N = S1.length(); // Function Call answerQueries(S1, S2, N, T, Q); // Input 2 String S11 = "aaab" ; String S21 = "bbba" ; int [][] Q1 = {{ 2 , 1 , 3 , 2 , 4 }, { 3 }, { 2 , 1 , 2 , 2 , 2 }, { 3 }, { 2 , 1 , 4 , 2 , 1 }, { 3 }, { 2 , 1 , 2 , 2 , 1 }, { 3 }}; int T1 = 2 ; int N1 = S11.length(); // Function Call answerQueries(S11, S21, N1, T1, Q1); } } |
Python3
from collections import deque # Function to answer following three types of queries def answer_queries(S1, S2, N, T, Q): # current score of the string indicates the number of characters that are equal currently cur_score = 0 # iterating over the string to find the score for i in range (N): if S1[i] = = S2[i]: cur_score + = 1 # queue for tracking blocked positions q = deque() # iterating for all queries for i in range ( len (Q)): # characters unblocking if q and q[ 0 ] = = i: idx = i - T q.popleft() if S1[idx] ! = S2[idx]: cur_score - = 1 # type of query type = Q[i][ 0 ] if type = = 1 : # position of the element which will be blocked pos = Q[i][ 1 ] # the position we are blocking, if it is not equal then increase the current score if S1[pos - 1 ] ! = S2[pos - 1 ]: cur_score + = 1 # inserting the position of the query when blocked characters # will be unblocked at the given index q.append(i + T) elif type = = 2 : # string1 will be either S1(1) or S2(2) and the position # pos1 which we have to swap with # string2's either S1(1) or S2(2) and the position pos2 string1, pos1, string2, pos2 = Q[i][ 1 ], Q[i][ 2 ], Q[i][ 3 ], Q[i][ 4 ] # if those positions are equal then subtract 1 from curScore for each position # since we are going to swap them if S1[pos1 - 1 ] = = S2[pos1 - 1 ]: cur_score - = 1 if pos1 ! = pos2 and S1[pos2 - 1 ] = = S2[pos2 - 1 ]: cur_score - = 1 # if character from S1 is swapped with character from S1 only if string1 = = 1 and string2 = = 1 : S1 = list (S1) S1[pos1 - 1 ], S1[pos2 - 1 ] = S1[pos2 - 1 ], S1[pos1 - 1 ] S1 = ''.join(S1) # if character from S1 is swapped with character from S2 elif string1 = = 1 and string2 = = 2 : S1 = list (S1) S2 = list (S2) S1[pos1 - 1 ], S2[pos2 - 1 ] = S2[pos2 - 1 ], S1[pos1 - 1 ] S1 = ''.join(S1) S2 = ''.join(S2) # if character from S2 is swapped with character from S1 elif string1 = = 2 and string2 = = 1 : S1 = list (S1) S2 = list (S2) S2[pos1 - 1 ], S1[pos2 - 1 ] = S1[pos2 - 1 ], S2[pos1 - 1 ] S1 = ''.join(S1) S2 = ''.join(S2) # if character from S2 is swapped with character from S2 else : S2 = list (S2) S2[pos1 - 1 ], S2[pos2 - 1 ] = S2[pos2 - 1 ], S2[pos1 - 1 ] S2 = ''.join(S2) # if those positions are equal then add 1 to curScore for each position if S1[pos1 - 1 ] = = S2[pos1 - 1 ]: cur_score + = 1 if pos1 ! = pos2 and S1[pos2 - 1 ] = = S2[pos2 - 1 ]: cur_score + = 1 else : # if the current score is equal to N, then print YES, else print NO if cur_score = = N: print ( "YES" , end = ' ' ) else : print ( "NO" , end = ' ' ) print () # Driver Code if __name__ = = '__main__' : # Input 1 S1 = "cool" S2 = "club" Q = [[ 2 , 1 , 2 , 2 , 3 ], [ 2 , 2 , 2 , 2 , 4 ], [ 1 , 2 ], [ 3 ], [ 3 ]] T = 2 N = len (S1) # Function Call answer_queries(S1, S2, N, T, Q) # Input 2 S11 = "aaab" S21 = "bbba" Q1 = [[ 2 , 1 , 3 , 2 , 4 ], [ 3 ], [ 2 , 1 , 2 , 2 , 2 ], [ 3 ], [ 2 , 1 , 4 , 2 , 1 ], [ 3 ], [ 2 , 1 , 2 , 2 , 1 ], [ 3 ]] T1 = 2 N1 = len (S11) # Function Call answer_queries(S11, S21, N1, T1, Q1) |
C#
using System; using System.Collections.Generic; class Program { static void AnswerQueries( string S1, string S2, int N, int T, List< int []> Q) { // current score of the string indicates the number of characters that are equal currently int curScore = 0; // iterating over the string to find the score for ( int i = 0; i < N; i++) { if (S1[i] == S2[i]) { curScore += 1; } } // queue for tracking blocked positions Queue< int > q = new Queue< int >(); // iterating for all queries for ( int i = 0; i < Q.Count; i++) { // characters unblocking if (q.Count > 0 && q.Peek() == i) { int idx = i - T; q.Dequeue(); if (S1[idx] != S2[idx]) { curScore -= 1; } } // type of query int type = Q[i][0]; if (type == 1) { // position of the element which will be blocked int pos = Q[i][1]; // the position we are blocking, if it is not equal then increase the current score if (S1[pos - 1] != S2[pos - 1]) { curScore += 1; } // inserting the position of the query when blocked characters // will be unblocked at the given index q.Enqueue(i + T); } else if (type == 2) { // string1 will be either S1(1) or S2(2) and the position // pos1 which we have to swap with // string2's either S1(1) or S2(2) and the position pos2 int string1 = Q[i][1], pos1 = Q[i][2], string2 = Q[i][3], pos2 = Q[i][4]; // if those positions are equal then subtract 1 from curScore for each position // since we are going to swap them if (S1[pos1 - 1] == S2[pos1 - 1]) { curScore -= 1; } if (pos1 != pos2 && S1[pos2 - 1] == S2[pos2 - 1]) { curScore -= 1; } // if character from S1 is swapped with character from S1 only if (string1 == 1 && string2 == 1) { char [] s1Array = S1.ToCharArray(); char temp = s1Array[pos1 - 1]; s1Array[pos1 - 1] = s1Array[pos2 - 1]; s1Array[pos2 - 1] = temp; S1 = new string (s1Array); } // if character from S1 is swapped with character from S2 else if (string1 == 1 && string2 == 2) { char [] s1Array = S1.ToCharArray(); char [] s2Array = S2.ToCharArray(); char temp = s1Array[pos1 - 1]; s1Array[pos1 - 1] = s2Array[pos2 - 1]; s2Array[pos2 - 1] = temp; S1 = new string (s1Array); S2 = new string (s2Array); } // if character from S2 is swapped with character from S1 else if (string1 == 2 && string2 == 1) { char [] s1Array = S1.ToCharArray(); char [] s2Array = S2.ToCharArray(); char temp = s2Array[pos1 - 1]; s2Array[pos1 - 1] = s1Array[pos2 - 1]; s1Array[pos2 - 1] = temp; S1 = new string (s1Array); S2 = new string (s2Array); } // if character from S2 is swapped with character from S2 else { char [] s2Array = S2.ToCharArray(); char temp = s2Array[pos1 - 1]; s2Array[pos1 - 1] = s2Array[pos2 - 1]; s2Array[pos2 - 1] = temp; S2 = new string (s2Array); } // if those positions are equal then add 1 to curScore for each position if (S1[pos1 - 1] == S2[pos1 - 1]) { curScore += 1; } if (pos1 != pos2 && S1[pos2 - 1] == S2[pos2 - 1]) { curScore += 1; } } else { // if the current score is equal to N, then print YES, else print NO if (curScore == N) { Console.Write( "YES " ); } else { Console.Write( "NO " ); } } } Console.WriteLine(); } // Driver Code static void Main() { // Input 1 string S1 = "cool" ; string S2 = "club" ; List< int []> Q = new List< int []> { new int [] { 2, 1, 2, 2, 3 }, new int [] { 2, 2, 2, 2, 4 }, new int [] { 1, 2 }, new int [] { 3 }, new int [] { 3 } }; int T = 2; int N = S1.Length; // Function Call AnswerQueries(S1, S2, N, T, Q); // Input 2 string S11 = "aaab" ; string S21 = "bbba" ; List< int []> Q1 = new List< int []> { new int [] { 2, 1, 3, 2, 4 }, new int [] { 3 }, new int [] { 2, 1, 2, 2, 2 }, new int [] { 3 }, new int [] { 2, 1, 4, 2, 1 }, new int [] { 3 }, new int [] { 2, 1, 2, 2, 1 }, new int [] { 3 } }; int T1 = 2; int N1 = S11.Length; // Function Call AnswerQueries(S11, S21, N1, T1, Q1); } } |
Javascript
function GFG(S1, S2, N, T, Q) { // current score of the string indicates the number of // characters that are equal currently let curScore = 0; // iterating over the string to find the score for (let i = 0; i < N; i++) { if (S1.charAt(i) == S2.charAt(i)) { curScore += 1; } } // queue for tracking blocked positions let q = []; // iterating for all queries for (let i = 0; i < Q.length; i++) { // characters unblocking if (q.length > 0 && q[0] == i) { let idx = i - T; q.shift(); if (S1.charAt(idx) != S2.charAt(idx)) { curScore -= 1; } } // type of query let type = Q[i][0]; if (type == 1) { // position of the element which will be blocked let pos = Q[i][1]; // the position we are blocking // if it is not equal then increase the current score if (S1.charAt(pos - 1) != S2.charAt(pos - 1)) { curScore += 1; } q.push(i + T); } else if (type == 2) { // string1 will be either S1(1) or S2(2) and the position // pos1 which we have to swap with // string2's either S1(1) or S2(2) let string1 = Q[i][1]; let pos1 = Q[i][2]; let string2 = Q[i][3]; let pos2 = Q[i][4]; // if those positions are equal then subtract 1 from curScore for each position since we are going to swap them if (S1.charAt(pos1 - 1) == S2.charAt(pos1 - 1)) { curScore -= 1; } if (pos1 != pos2 && S1.charAt(pos2 - 1) == S2.charAt(pos2 - 1)) { curScore -= 1; } // if character from S1 is swapped with character from S1 only if (string1 == 1 && string2 == 1) { let s1Array = S1.split(' '); [s1Array[pos1 - 1], s1Array[pos2 - 1]] = [s1Array[pos2 - 1], s1Array[pos1 - 1]]; S1 = s1Array.join(' '); } else if (string1 == 1 && string2 == 2) { let s1Array = S1.split(' '); let s2Array = S2.split(' '); [s1Array[pos1 - 1], s2Array[pos2 - 1]] = [s2Array[pos2 - 1], s1Array[pos1 - 1]]; S1 = s1Array.join(' '); S2 = s2Array.join(' '); // if character from S2 is swapped with the character from S1 } else if (string1 == 2 && string2 == 1) { let s1Array = S1.split(' '); let s2Array = S2.split(' '); [s2Array[pos1 - 1], s1Array[pos2 - 1]] = [s1Array[pos2 - 1], s2Array[pos1 - 1]]; S1 = s1Array.join(' '); S2 = s2Array.join(' '); // if character from S2 is swapped with character from S2 } else { let s2Array = S2.split(' '); [s2Array[pos1 - 1], s2Array[pos2 - 1]] = [s2Array[pos2 - 1], s2Array[pos1 - 1]]; S2 = s2Array.join(' '); } // if those positions are equal then add // 1 to curScore for each position if (S1.charAt(pos1 - 1) == S2.charAt(pos1 - 1)) { curScore += 1; } if (pos1 != pos2 && S1.charAt(pos2 - 1) == S2.charAt(pos2 - 1)) { curScore += 1; } } else { // if the current score is equal to N, then print YES, else print NO if (curScore == N) { process.stdout.write( "YES " ); } else { process.stdout.write( "NO " ); } } } console.log(); } // Driver Code let S1 = "cool" ; let S2 = "club" ; let Q = [[2, 1, 2, 2, 3], [2, 2, 2, 2, 4], [1, 2], [3], [3]]; let T = 2; let N = S1.length; // Function Call GFG(S1, S2, N, T, Q); // Input 2 let S11 = "aaab" ; let S21 = "bbba" ; let Q1 = [[2, 1, 3, 2, 4], [3], [2, 1, 2, 2, 2], [3], [2, 1, 4, 2, 1], [3], [2, 1, 2, 2, 1], [3]]; let T1 = 2; let N1 = S11.length; // Function Call GFG(S11, S21, N1, T1, Q1); |
YES YES NO NO NO NO
Time Complexity: O(N + Q)
Auxiliary Space: O(N)
Contact Us