Given a string S of length 2N and Q Queries containing three integers T, A, and B each, where queries can be of the following two types:
- T=1: Swap the Ath and Bth characters in S.(In 1-based indexing)
- T=2: Swap the first N characters with the last N characters i.e “ABCD” becomes “CDAB”
The task is to find the final string after applying the Q Queries to it.
Examples:
Input: S=”ABCD”, N=2, Q={{2, 0, 0}, {1, 1, 3}, {2, 0, 0}}
Output:
CBAD
Explanation:
After 1st query: S=”CDAB”
After 2nd query: S=”ADCB”
After 3rd query: S=”CBAD”Input: S=”GEEK”, N=2, Q={{2, 0, 0}, {1, 1, 2}, {1, 2, 3}, {1, 3, 4}, {2, 0, 0}}
Output:
EEKG
Naive Approach: Follow the steps below to solve the problem:
- Traverse the Queries array, and for each current index i, do the following:
- Extract T, A and B as T=Q[i][0], A=Q[i][1] and B=Q[i][2].
- Decrement A and B both to make them 0-indexed.
- If T is equal to 1, swap the characters at index A and B respectively.
- Otherwise, Traverse the string from 0 to N-1 and swap each A[j] with A[j+N].
- Print the string S
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find final string // after applying all Queries on it void solve(string S, int N, vector<vector< int > > Queries, int Q) { // Traverse the Queries array for ( int i = 0; i < Q; i++) { int T = Queries[i][0], A = Queries[i][1], B = Queries[i][2]; // convert A, B to zero indexing A--; B--; // Query of 1st type if (T == 1) { // swap ath and bth characters swap(S[A], S[B]); } // Query of 2nd type else { // swap first N characters // with last N characters for ( int j = 0; j < N; j++) { swap(S[j], S[j + N]); } } } // Print answer cout << S << endl; } // Driver code int main() { // Input string S = "ABCD" ; int N = S.length() / 2; vector<vector< int > > Queries = { { 2, 0, 0 }, { 1, 1, 3 }, { 2, 0, 0 } }; int Q = Queries.size(); // Function call solve(S, N, Queries, Q); return 0; } |
Java
import java.util.*; class Main { // Function to find final string // after applying all Queries on it static void solve(String S, int N, List<List<Integer> > Queries, int Q) { // Traverse the Queries array for ( int i = 0 ; i < Q; i++) { int T = Queries.get(i).get( 0 ), A = Queries.get(i).get( 1 ), B = Queries.get(i).get( 2 ); // convert A, B to zero indexing A--; B--; // Query of 1st type if (T == 1 ) { // swap ath and bth characters char [] sArr = S.toCharArray(); char temp = sArr[A]; sArr[A] = sArr[B]; sArr[B] = temp; S = new String(sArr); } // Query of 2nd type else { // swap first N characters // with last N characters char [] sArr = S.toCharArray(); for ( int j = 0 ; j < N; j++) { char temp = sArr[j]; sArr[j] = sArr[j + N]; sArr[j + N] = temp; } S = new String(sArr); } } // Print answer System.out.println(S); } // Driver code public static void main(String[] args) { // Input String S = "ABCD" ; int N = S.length() / 2 ; List<List<Integer> > Queries = Arrays.asList( Arrays.asList( 2 , 0 , 0 ), Arrays.asList( 1 , 1 , 3 ), Arrays.asList( 2 , 0 , 0 )); int Q = Queries.size(); // Function call solve(S, N, Queries, Q); } } // This code is contributed by Jay |
Python3
# Python3 program for the above approach # Function to find final string # after applying all Queries on it def solve(S, N, Queries, Q): # Traverse the Queries array S = list (S) for i in range (Q): T = Queries[i][ 0 ] A = Queries[i][ 1 ] B = Queries[i][ 2 ] # Convert A, B to zero indexing A - = 1 B - = 1 # Query of 1st type if (T = = 1 ): # Swap ath and bth characters temp = S[A] S[A] = S[B] S[B] = temp # Query of 2nd type else : # Swap first N characters # with last N characters for j in range (N): temp = S[j] S[j] = S[j + N] S[j + N] = temp S = ''.join(S) # Print answer print (S) # Driver code if __name__ = = '__main__' : # Input S = "ABCD" N = len (S) / / 2 Queries = [ [ 2 , 0 , 0 ], [ 1 , 1 , 3 ], [ 2 , 0 , 0 ] ] Q = len (Queries) # Function call solve(S, N, Queries, Q) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class Solution { // Function to find final string // after applying all Queries on it static void Solve( string S, int N, List<List< int >> Queries, int Q) { // Traverse the Queries list for ( int i = 0; i < Q; i++) { int T = Queries[i][0], A = Queries[i][1], B = Queries[i][2]; // convert A, B to zero indexing A--; B--; // Query of 1st type if (T == 1) { // swap ath and bth characters char [] charArray = S.ToCharArray(); char temp = charArray[A]; charArray[A] = charArray[B]; charArray[B] = temp; S = new string (charArray); } // Query of 2nd type else { // swap first N characters // with last N characters char [] charArray = S.ToCharArray(); for ( int j = 0; j < N; j++) { char temp = charArray[j]; charArray[j] = charArray[j + N]; charArray[j + N] = temp; } S = new string (charArray); } } // Print answer Console.WriteLine(S); } // Driver code static void Main() { // Input string S = "ABCD" ; int N = S.Length / 2; List<List< int >> Queries = new List<List< int >> { new List< int > { 2, 0, 0 }, new List< int > { 1, 1, 3 }, new List< int > { 2, 0, 0 } }; int Q = Queries.Count; // Function call Solve(S, N, Queries, Q); } } |
Javascript
// Function to find final string after applying all Queries on it function solve(S, N, Queries, Q) { // Convert the string to an array of characters let arr = S.split( '' ); // Traverse the Queries array for (let i = 0; i < Q; i++) { let T = Queries[i][0]; let A = Queries[i][1]; let B = Queries[i][2]; // Convert A, B to zero indexing A -= 1; B -= 1; // Query of 1st type if (T === 1) { // Swap ath and bth characters let temp = arr[A]; arr[A] = arr[B]; arr[B] = temp; // Query of 2nd type } else { // Swap first N characters with last N characters for (let j = 0; j < N; j++) { let temp = arr[j]; arr[j] = arr[j + N]; arr[j + N] = temp; } } } // Convert the array back to string S = arr.join( '' ); // Print answer console.log(S); } // Driver code let S = "ABCD" ; let N = Math.floor(S.length / 2); let Queries = [ [ 2, 0, 0 ], [ 1, 1, 3 ], [ 2, 0, 0 ] ]; let Q = Queries.length; // Function call solve(S, N, Queries, Q); |
CBAD
Time Complexity: O(N*Q)
Auxiliary Space: O(1)
Efficient Approach: There is no need to actually swap first N characters with last N characters for every query of type 2. This can be done once at the end by keeping track of how many times this is done in a separate variable. Follow the steps below to solve the problem:
- Initialize a variable flip to 0, which keeps track of how many times a query of type 2 is performed on S.
- Traverse the Queries array, and for each current index i, do the following:
- Extract T, A and B as T=Q[i][0], A=Q[i][1] and B=Q[i][2].
- Decrement A and B both to make them 0-indexed.
- If T is equal to 1, do the following:
- Otherwise, increment flip
- Check if flip is even. If it is, print S as it is.
- Otherwise, S is flipped, so print the last N characters of S first and then, the first N characters of S.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find final string // after applying all Queries on it void solve(string S, int N, vector<vector< int > > Queries, int Q) { int flip = 0; // Traverse the Queries array for ( int i = 0; i < Q; i++) { int T = Queries[i][0], A = Queries[i][1], B = Queries[i][2]; // convert A, B to zero indexing A--; B--; // Query of 1st type if (T == 1) { // simply swap the character at // Ath and Bth index if (flip % 2 == 0) swap(S[A], S[B]); else { // add N to A, B as string starts at nth // index(0 indexing) and take mod with size // of string (2*N) and swap the character at // Ath and Bth index calculated. A = (A + N) % (2 * N); B = (B + N) % (2 * N); swap(S[A], S[B]); } } // Query of 2nd type else { // increment flip flip++; } } // Print answer if (flip % 2 == 0) cout << S << endl; else { // string starts at Nth index; for ( int i = N; i < 2 * N; i++) cout << S[i]; for ( int i = 0; i < N; i++) cout << S[i]; cout << endl; } } // Driver code int main() { // Input string S = "ABCD" ; int N = S.length() / 2; vector<vector< int > > Queries = { { 2, 0, 0 }, { 1, 1, 3 }, { 2, 0, 0 } }; int Q = Queries.size(); // Function call solve(S, N, Queries, Q); return 0; } |
Java
import java.util.*; class Main { // Function to find final string // after applying all Queries on it static void solve(String S, int N, List<List<Integer> > Queries, int Q) { int flip = 0 ; // Traverse the Queries array for ( int i = 0 ; i < Q; i++) { int T = Queries.get(i).get( 0 ), A = Queries.get(i).get( 1 ), B = Queries.get(i).get( 2 ); // convert A, B to zero indexing A--; B--; // Query of 1st type if (T == 1 ) { // simply swap the character at // Ath and Bth index if (flip % 2 == 0 ) S = swap(S, A, B); else { // add N to A, B as string starts at nth // index(0 indexing) and take mod with // size of string (2*N) and swap the // character at Ath and Bth index // calculated. A = (A + N) % ( 2 * N); B = (B + N) % ( 2 * N); S = swap(S, A, B); } } // Query of 2nd type else { // increment flip flip++; } } // Print answer if (flip % 2 == 0 ) System.out.println(S); else { // string starts at Nth index; for ( int i = N; i < 2 * N; i++) System.out.print(S.charAt(i)); for ( int i = 0 ; i < N; i++) System.out.print(S.charAt(i)); System.out.println(); } } // Function to swap characters at indices i and j static String swap(String S, int i, int j) { char [] arr = S.toCharArray(); char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return new String(arr); } // Driver code public static void main(String[] args) { // Input String S = "ABCD" ; int N = S.length() / 2 ; List<List<Integer> > Queries = Arrays.asList( Arrays.asList( 2 , 0 , 0 ), Arrays.asList( 1 , 1 , 3 ), Arrays.asList( 2 , 0 , 0 )); int Q = Queries.size(); // Function call solve(S, N, Queries, Q); } } // This code is contributed by Jay |
Python3
# Function to find final string # after applying all Queries on it def solve(st, N, Queries, Q): flip = 0 # Queries array traverse for i in range (Q): T, A, B = Queries[i] # convert A, B to zero indexing A - = 1 B - = 1 # 1st Query if T = = 1 : # swap the character at Ath and Bth index if flip % 2 = = 0 : st[A], st[B] = st[B], st[A] else : # add N to A, B as string starts at nth # index(0 indexing) and take mod with size # of string (2*N) and swap the character at # Ath and Bth index calculated. A = (A + N) % ( 2 * N) B = (B + N) % ( 2 * N) st[A], st[B] = st[B], st[A] # 2nd Query else : # increment flip flip + = 1 # Print answer if flip % 2 = = 0 : print (''.join(st)) else : # string starts at Nth index; ans = [] for i in range (N, 2 * N): ans.append(S[i]) for i in range (N): ans.append(S[i]) print (''.join(ans)) # Driver code if __name__ = = '__main__' : # Input taken str = "ABCD" N = len ( str ) / / 2 Queries = [[ 2 , 0 , 0 ], [ 1 , 1 , 3 ], [ 2 , 0 , 0 ]] Q = len (Queries) # call the solve function solve( list ( str ), N, Queries, Q) |
C#
using System; using System.Collections.Generic; using System.Linq; class MainClass { // Function to find final string // after applying all Queries on it static void Solve( string S, int N, List<List< int >> Queries, int Q) { int flip = 0; // Traverse the Queries array for ( int i = 0; i < Q; i++) { int T = Queries[i][0], A = Queries[i][1], B = Queries[i][2]; // convert A, B to zero indexing A--; B--; // Query of 1st type if (T == 1) { // simply swap the character at // Ath and Bth index if (flip % 2 == 0) S = Swap(S, A, B); else { // add N to A, B as string starts at nth // index(0 indexing) and take mod with // size of string (2*N) and swap the // character at Ath and Bth index // calculated. A = (A + N) % (2 * N); B = (B + N) % (2 * N); S = Swap(S, A, B); } } // Query of 2nd type else { // increment flip flip++; } } // Print answer if (flip % 2 == 0) Console.WriteLine(S); else { // string starts at Nth index; for ( int i = N; i < 2 * N; i++) Console.Write(S[i]); for ( int i = 0; i < N; i++) Console.Write(S[i]); Console.WriteLine(); } } // Function to swap characters at indices i and j static string Swap( string S, int i, int j) { char [] arr = S.ToCharArray(); char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return new string (arr); } // Driver code public static void Main() { // Input string S = "ABCD" ; int N = S.Length / 2; List<List< int >> Queries = new List<List< int >>() { new List< int > {2, 0, 0}, new List< int > {1, 1, 3}, new List< int > {2, 0, 0} }; int Q = Queries.Count(); // Function call Solve(S, N, Queries, Q); }} |
Javascript
// Function to find final string // after applying all Queries on it function solve(S, N, Queries, Q) { let flip = 0; // Traverse the Queries array for (let i = 0; i < Q; i++) { let T = Queries[i][0], A = Queries[i][1], B = Queries[i][2]; // convert A, B to zero indexing A--; B--; // Query of 1st type if (T === 1) { // simply swap the character at // Ath and Bth index if (flip % 2 === 0) { S = swap(S, A, B); } else { // add N to A, B as string starts at nth // index(0 indexing) and take mod with // size of string (2*N) and swap the // character at Ath and Bth index // calculated. A = (A + N) % (2 * N); B = (B + N) % (2 * N); S = swap(S, A, B); } } // Query of 2nd type else { flip++; // increment flip } } // Print answer if (flip % 2 === 0) { console.log(S); } else { // string starts at Nth index; let result = '' ; for (let i = N; i < 2 * N; i++) { result += S.charAt(i); } for (let i = 0; i < N; i++) { result += S.charAt(i); } console.log(result); }} // Function to swap characters at indices i and j function swap(S, i, j) { let arr = S.split( '' ); let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr.join( '' ); } // Code start const S = 'ABCD' ; // Input const N = Math.floor(S.length / 2); const Queries = [[2, 0, 0], [1, 1, 3], [2, 0, 0]]; const Q = Queries.length; // Calling the function solve(S, N, Queries, Q); |
CBAD
Time Complexity: O(N+Q)
Auxiliary Space: O(1)