# Flip the String by either swapping given characters or rotating it horizontally for Q queries

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.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input:S=”ABCD”, N=2, Q={{2, 0, 0}, {1, 1, 3}, {2, 0, 0}}Output:

CBADExplanation:

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].**

- Extract
- 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;` `}` |

## 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` |

**Output**

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**

- Extract
- 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;` `}` |

**Output**

CBAD

**Time Complexity: **O(N+Q)**Auxiliary Space: **O(1)