# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Pranav Dev

Tester: Abhinav Sharma, Aryan

Editorialist: Lavish Gupta

# DIFFICULTY:

Cakewalk

# PREREQUISITES:

None

# PROBLEM:

Chef is working on his swap-based sorting algorithm for strings.

Given a string S of length N, he wants to know whether he can sort the string using his algorithm.

According to the algorithm, one can perform the following operation on string S any number of times:

- Choose some index i (1 \leq i \leq N) and swap the i^{th} character from the front and the i^{th} character from the back.

More formally, choose an index i and swap S_i and S_{(N+1-i)}.

For example, \underline{\texttt{d}} \texttt{cb} \underline{\texttt{a}} can be converted to \underline{\texttt{a}} \texttt{cb} \underline{\texttt{d}} using one operation where i = 1.

Help Chef find if it is possible to sort the string using **any** (possibly zero) number of operations.

# EXPLANATION:

Let us first find out the string that the Chef will end up with, given that he performs the swap optimally.

Let us consider the index i and j = (N+1-i). Also, let i \leq j. If S_i \leq S_j then we do not need to swap these characters (as they are in already in correct order). Otherwise, we will swap S_i and S_j.

Let us first perform the above operation by iterating over the complete string, and let us denote the final string as S'. If S' is sorted, then our answer is **YES**, otherwise our answer will be **NO**.

To check if S' is sorted, we can iterate over the string and check that S_i \leq S_{i+1} for all i such that 1 \leq i \leq N-1. Another way to check is to use the sort function which is usually present in the Standard Template Library (or similar libraries) in most of the languages.

# TIME COMPLEXITY:

O(N) or O(N\cdot \log{N}) for each test case, depending on the implementation details.

# SOLUTION:

## Editorialist's Solution

```
#define ll long long
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>
using namespace std ;
void solve()
{
ll n ;
cin >> n ;
string a , b ;
cin >> a ;
b = a ;
sort(b.begin() , b.end()) ;
for(int i = 0 ; i < n ; i++)
{
int j = (n-1-i) ;
if(j < i)
break ;
if(a[i] > a[j])
swap(a[i] , a[j]) ;
}
if(a == b)
cout << "YES\n" ;
else
cout << "NO\n" ;
return ;
}
int main()
{
ll t = 1 ;
cin >> t ;
while(t--)
{
solve() ;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
```