PROBLEM LINK:
Setter: Ankush Chhabra
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
EASY
PREREQUISITES:
Prefix sums
PROBLEM:
We are given a string of size N consisting of only uppercase letters. A K - magical string is that string which has the length of longest non-decreasing subsequence equal to K . Given queries of the form L, R we need to determine if the substring from L to R can be converted into a K - magical string by rearranging the characters. If multiple such strings exist, we need to output the lexicographically largest one possible.
QUICK EXPLANATION:
-
Let us calculate cnt_j which is the count of character j from L to R for every j from 1 to 26. This can be done by prefix sums.
-
Let max be the maximum element in cnt.
-
If R-L+1<K or max \gt K, no answe is possible.
-
Let T be the string in which all the characters in the positions from L to R are sorted in decreasing order.
-
If max =K, we can directly output T as our answer. Else max \lt K, in this case we reverse the last K chracters in T and output the modified T as our answer.
EXPLANATION:
Let us initially preprocess the array pref before answering queries. pref_{i,j} denotes the total number of characters equal to j^{th} uppercase alphabet for all the indices from 1 to i.
If R-L+1 \lt K, we clearly can’t have an answer as the size of a K- magical string must be atleast K.
Let us now consider R-L+1 \geq K.
Let us calculate cnt using pref where cnt_j is the total number of characters equal to j^{th} uppercase alphabet for all the indices from L to R. Let max be the maximum value in the cnt array.
Let us also consider string T which is all the character in the substring from L to R sorted in decreasing order.
Now consider the following three cases:
Case 1: \hspace{1 mm} max \gt K
- In this case, we cannot have an answer. This is beacuse we have an alphabet which is repeated more than K times. Then, the maximum non-decreasing subsequence of any rearranged string will be more than K because we always have a non-decreasing subsequence consisting of only this alphabet which has size max \gt K.
Case 2: \hspace{1 mm} max = K
- In this case, we can just output the lexicographically largest string possible i.e, T. This is because the maximum non-decreasing subsequence of T is the maxmimum count over all alphabets which is max = K.
Case 3: \hspace{1 mm} max \lt K
- In this case we need to modify T to increasing the maximum non-decreasing subsequence from max to K and also keep T as lexicographically large as possible. We can go about it by simply reversing the last K positions of T. Then, the last K positions are non-dereasing thus changing the maximum size of non-decreasing subsequence to K.
TIME COMPLEXITY:
O(26 \cdot S + X) where S is the total number of queries overall all testcases and X is the the sum of (R−L+1) over all Q queries over all test cases.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;
string s;
cin >> s;
vector<vector<int>> pref(n, vector<int>(26));
for (int i = 0; i < n; i++)
{
if (i)
for (int j = 0; j < 26; j++)
{
pref[i][j] = pref[i - 1][j];
}
pref[i][s[i] - 'A']++;
}
int q;
cin >> q;
while (q--)
{
int l, r, k;
cin >> l >> r >> k;
l--;
r--;
if (r - l + 1 < k)
{
cout << "No" << "\n";
continue;
}
int max_cnt = 0;
for (int i = 0; i < 26; i++)
{
if (l)
max_cnt = max(max_cnt, pref[r][i] - pref[l - 1][i]);
else
max_cnt = max(max_cnt, pref[r][i]);
}
if (max_cnt > k)
{
cout << "No" << "\n";
continue;
}
cout << "Yes" << "\n";
string t = s.substr(l, r - l + 1);
sort(t.rbegin(), t.rend());
if (max_cnt < k)
reverse(t.end() - k, t.end());
cout << t << "\n";
}
}
}
Setter's solution
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define ii insert
#define mem(l,r) memset(l,r,sizeof(l))
#define sorta(a,n) sort(a+1,a+1+n)
#define sortv(v) sort(v.begin(),v.end())
#define revs(s) reverse(s.begin(),s.end())
#define fastio ios::sync_with_stdio(false), cin.tie(NULL);
const int N=1e5+5;
const int mod=1e9+7;
const ll int_max=1e18;
const ll int_min=-1e18;
#define rep(i,j,k) for(ll i=j;i<=k;i++)
#define repr(i,j,k) for(ll i=j;i>=k;i--)
using namespace std;
ll sum=0;
void solve()
{
ll n;
cin>>n;
assert(n>=1 && n<=100000);
vector<vector<ll>>prefix(n+2,vector<ll>(28,0));
string s;
cin>>s;
rep(i,0,n-1)
{
assert(s[i]>='A' && s[i]<='Z');
}
prefix[0][s[0]-'A']=1;
rep(i,1,n-1)
{
rep(j,0,25)
{
prefix[i][j]=prefix[i-1][j];
}
prefix[i][s[i]-'A']+=1;
}
ll q;
cin>>q;
assert(q>=1 && q<=100000);
while(q--)
{
ll l,r,k;
cin>>l>>r>>k;
assert(k>=1 && k<=n);
assert(l>=1 && l<=n);
assert(r>=1 && r<=n);
assert(l<=r);
l--;
r--;
ll sz=(r-l+1);
if(sz<k)
{
cout<<"No"<<'\n';
continue;
}
ll mx=0;
rep(i,0,25)
{
ll freq=prefix[r][i]-prefix[l][i]+((s[l]-'A')==i);
mx=max(mx,freq);
}
if(mx>k)
{
cout<<"No"<<'\n';
continue;
}
cout<<"Yes"<<'\n';
sum+=(r-l+1);
if(k==mx)
{
string ans;
rep(i,l,r)
{
ans+=s[i];
}
sort(ans.begin(),ans.end(),greater<char>());
cout<<ans<<'\n';
continue;
}
map<char,ll>freq;
rep(i,l,r)
{
freq[s[i]]++;
}
ll cnt=(sz-k);
for(char i='Z';i>='A';i--)
{
if(cnt==0)
break;
if(freq[i]>0)
{
cnt--;
cout<<(i);
freq[i]--;
}
if(freq[i]!=0)
i++;
}
cnt=k;
for(char i='A';i<='Z';i++)
{
if(cnt==0)
break;
if(freq[i]>0)
{
cnt--;
cout<<i;
freq[i]--;
}
if(freq[i]!=0)
i--;
}
cout<<'\n';
}
}
int main() {
fastio
int t;
cin>>t;
while(t--)
{
solve();
}
assert(sum>=0 && sum<=1000000);
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
int a[n][26];
int cnt[26] = {};
for(int i = 0; i < n; i++){
for(int j = 0; j < 26; j++){
a[i][j] = cnt[j] + (s[i] - 'A' == j);
cnt[j] = a[i][j];
}
}
int q;
cin>>q;
while(q--){
int l, r, k;
cin>>l>>r>>k;
if(r - l + 1 < k){
cout<<"No\n";
continue;
}
l--;
r--;
int mx = 0;
for(int i = 0; i < 26; i++){
mx = max(mx, a[r][i] - a[l][i] + (s[l] - 'A' == i));
}
if(mx > k){
cout<<"No\n";
}else{
cout<<"Yes\n";
string temp = s.substr(l, r - l + 1);
sort(temp.begin(), temp.end());
if(mx == k){
k = 0;
}
for(int i = r - l; i >= k; i--){
cout<<temp[i];
}
for(int i = 0; i < k; i++){
cout<<temp[i];
}
cout<<"\n";
}
}
}
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions. 