PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You’re given a string S. Find the lexicographically smallest subsequence that can be removed from S so that the resulting string cannot be rearranged to to form a palindrome.
EXPLANATION:
To begin, we need to know when exactly a string can be rearranged to form a palindrome.
This is fairly well-known: a string can be rearranged to form a palindrome if and only if at most one of its characters has an odd frequency.
We want a string to not be able to form a palindrome, so two or more of its characters should have odd frequencies.
In particular, if S already satisfies this condition, nothing needs to be deleted - the answer is just the empty subsequence.
Now we only deal with the case where 0 or 1 character has an odd frequency.
First, let’s get an edge case out of the way: if all the characters of S are equal, it’s impossible to achieve what we want: no matter what we do, S will remain a palindrome.
So, in this case the answer is -1.
In all other cases, a valid subsequence exists (for example, we can delete all but two distinct characters), so our focus is only on finding the lexicographically smallest subsequence.
Lexicographic minimization generally suggests a greedy strategy: make the first character as small as possible (even at the cost of everything after it), then minimize the second, then the third, and so on.
Let’s try to do this.
Suppose the distinct characters appearing in S are c_1, c_2, \ldots, c_m in ascending order.
Let’s try to make c_1 the first character, and see what needs to be done.
First, it’s best to choose the leftmost occurrence of c_1: this gives us more choices to work with in the future, after all.
Let this leftmost occurrence be at index i_1.
Deleting one occurrence of c_1 changes the parity of its frequency, and we now have some suffix of S (from index i_1 + 1) to work with.
There are three possibilities:
- Two characters have odd frequency.
- Here, we’ve achieved our goal so we can stop immediately: deleting any more characters won’t help with lexicographic minimization, after all.
- One character has an odd frequency.
- We can only change the frequency of any character that appears after i_1.
- If any character appearing after i_1 has an even frequency, we’re good - its frequency can be made odd by deleting one occurrence.
- If no character after i_1 has an even frequency, we’ll never be able to achieve our goal of having two characters with even frequencies - so deleting this instance of c_1 isn’t valid and we’ll have to try with a larger character.
- Zero characters have odd frequency.
- Just as in the previous case, only characters that appear after i_1 can have their frequencies modified.
- So, there must be at least two distinct characters after i_1, otherwise we cannot achieve our goal.
Given that we only care about elements in the suffix, it’s enough to maintain the last occurrence of each character, and its frequency, to perform this check.
A direct implementation of this algorithm runs in \mathcal{O}(26^2\cdot N) time, with upto 26 choices for each character of the subsequence (which can have length till N), and then performing the check for each one by looking at all existing characters.
This is enough to get AC.
TIME COMPLEXITY:
\mathcal{O}(N\cdot 26^2) per testcase.
CODE:
Author's code (C++)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <chrono>
#include <random>
#include <set>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
while(kitne_cases_hain--){
ll n;
cin>>n;
string s;
cin>>s;
set <char> uniq;
ll cnt[n+1][26];
ll next[n+1][26];
for(int i=0;i<26;i++){
next[n][i]=n;
cnt[n][i]=0;
}
for(int i=n-1;i>=0;i--){
uniq.insert(s[i]);
for(int j=0;j<26;j++){
cnt[i][j]=cnt[i+1][j];
next[i][j]=next[i+1][j];
}
cnt[i][s[i]-'a']++;
if((i+1)<n){
next[i][s[i+1]-'a']=i+1;
}
}
ll parity[26]={};
for(int i=0;i<26;i++){
if(cnt[0][i]%2==0){
parity[i]=1;
}
}
ll curr[26];
ll pos;
for(int i=0;i<26;i++){
curr[i]=next[0][i];
}
curr[s[0]-'a']=0;
if(uniq.size()==1){
cout<<"-1\n";
continue;
}
string ans="";
ll total[26]={};
ll flag=0;
while(true){
flag=0;
for(int i=0;i<26;i++){
if((cnt[0][i]-total[i])%2){
flag++;
}
}
if(flag>=2){
break;
}
for(int i=0;i<26;i++){
if(curr[i]!=n){
flag=0;
pos=curr[i];
total[s[pos]-'a']++;
for(int j=0;j<26;j++){
if(cnt[pos+1][j]==0 && parity[j]==(total[j]%2)){
flag++;
continue;
}
if(cnt[pos+1][j]){
flag++;
}
}
total[s[pos]-'a']--;
if(flag>=2){
for(int j=0;j<26;j++){
curr[j]=next[pos][j];
}
ans+=s[pos];
total[s[pos]-'a']++;
break;
}
}
}
}
cout<<ans.size()<<"\n";
for(auto it:ans){
cout<<it;
}
cout<<"\n";
}
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
vector<int> freq(26);
for (auto c : s) freq[c - 'a'] ^= 1;
int odds = accumulate(begin(freq), end(freq), 0);
if (odds > 1) {
cout << 0 << '\n';
continue;
}
if (ranges::min(s) == ranges::max(s)) {
cout << -1 << '\n';
continue;
}
string ans = "";
vector<vector<int>> pos(26);
for (int i = 0; i < n; ++i)
pos[s[i] - 'a'].push_back(i);
for (int i = 0; i < 26; ++i)
ranges::reverse(pos[i]);
int L = 0, done = 0;
while (!done) {
for (int c = 0; c < 26; ++c) {
while (!pos[c].empty()) {
if (pos[c].back() < L) pos[c].pop_back();
else break;
}
if (pos[c].empty()) continue;
int i = pos[c].back();
odds -= freq[c];
freq[c] ^= 1;
odds += freq[c];
if (odds == 2) {
ans += 'a' + c;
done = 1;
break;
}
int good = 0;
if (odds == 1) {
// There must be an even char after i
for (int c2 = 0; c2 < 26; ++c2) {
if (freq[c2]) continue;
if (pos[c2].empty()) continue;
if (pos[c2][0] <= i) continue;
good = 2;
}
}
else {
// There must be two distinct chars after i
for (int c2 = 0; c2 < 26; ++c2) {
if (pos[c2].empty()) continue;
if (pos[c2][0] <= i) continue;
++good;
}
}
if (good >= 2) {
// Possible
ans += c + 'a';
L = i+1;
break;
}
else {
odds -= freq[c];
freq[c] ^= 1;
odds += freq[c];
}
}
}
cout << size(ans) << '\n' << ans << '\n';
}
}