Problem Statement
Contest Source
Author, Tester and Editorialist : Rohail Alam
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Fluency with observation-based problems
PROBLEM:
Given a string, you need to find out whether the characters can be arranged to obtain the lexicographically smallest form of the same with the help of swap operations bound by conditions mentioned in the problem statement.
QUICK EXPLANATION
Hint
Try to find out whether you can swap any two letters with the help of a vowel and a consonant.
EXPLANATION
This problem has a purely observation based solution. The answer will always be “YES” if there is at least one vowel and one consonant each in the given string. If not, the answer will still be “YES” if the string is already in the lexicographically smallest order, else the answer is “NO”.
To make the initial statement more clear, we can consider an example string “bayd”
The string we want to obtain after the swapping operations is “abdy”
First, we swap ‘a’ (vowel) with ‘b’ (consonant) to get “abyd”
Now we need to just swap ‘y’ and ‘d’ to get the desired string, but both of them are consonants so this is not possible to do directly. But observe that the presence of vowel ‘a’ aids in making this possible as such:
- Swap ‘a’ and ‘y’ to get “ybad”
- Move ‘d’ to the desired position by swapping ‘a’ and ‘d’ : “ybda”
- Move ‘a’ back to its original position by swapping ‘a’ and ‘y’ : “abdy”
Notice that through these steps we were able to swap two consonants with the help of a vowel.
From this observation, we can make out that the presence of at least 1 vowel and 1 consonant(to swap the vowel with) is a necessary and sufficient condition to obtain the desired string.
If the above condition is broken, then the answer is always “NO” as no swapping operation can be carried out, unless of course if the string is already in the lexicographically smallest order. In that case, the answer will be “YES”
SOLUTION
Click Me
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
string cpy = s;
sort(cpy.begin(),cpy.end()); // cpy is the lexicographically smallest form of s
set<char> vowels{'a','e','i','o','u'};
int vow=0,conso=0;
int size = (int)s.size();
for(int i=0;i<size;++i){
if(vowels.find(s[i]) == vowels.end()) conso++; // Counting the number of vowels and consonants in the given string
else vow++;
}
if(vow>=1 && conso>=1){
cout<<"YES\n"; // Condition described in the explanation is checked
}
else{
(s==cpy)? cout<<"YES\n" : cout<<"NO\n"; // If condition is not followed, checking if the given string is already in desired form
}
}
}