PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Sahil Chimnani
Tester: Rahul Dugar
Editorialist: Taranpreet Singh
DIFFICULTY
Simple
PREREQUISITES
Observations.
PROBLEM
Given a string S of lowercase English characters, you can obtain a coin by choosing and removing three characters from the string, if the three characters can be reordered to form a palindrome.
Find the maximum number of coins you can obtain.
QUICK EXPLANATION
The only condition removed characters should satisfy is that at least two of them must be the same. So the answer is bounded by X = \sum_{c} \lfloor \frac{f_c}{2}\rfloor where f_c denote frequency of character c in S. Also, for a string of length N, there cannot be more than N/3 operations.
So the number of gold coins obtained is min(X, |S|/3)
EXPLANATION
To get a gold coin, we always remove three characters from S, so we cannot obtain more than \displaystyle \Big \lfloor \frac{|S|}{3} \Big \rfloor. So \displaystyle \Big \lfloor \frac{|S|}{3} \Big \rfloor is an upper bound on answer.
Now, let’s see palindrome condition implies. Since we can rearrange three characters in any order, and then we need first character to be same as third character, this means that all three characters cannot be distinct.
This is it, every time we select three characters, atleast 2 of them must be same. Lets ignore middle character for now and consider counting the number of pairs of same characters they can form if no element appears in more than one pair. If a character c appears f_c times, we can form \displaystyle \Big \lfloor \frac{f_c}{2} \Big \rfloor pairs. Each of these pairs can be pick with any third character and this would form a valid triplet.
Hence, the number of pairs also impose an upper bound on the maximum number of gold coins attainable. Formally, if \displaystyle X = \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor denotes the total number of pairs of same characters, Then we cannot obtain more than X coins. Here A denotes the set of characters.
Considering both conditions, the maximum achievable gold coins is given by \displaystyle \text{min}\Big( \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor, \frac{|S|}{3}\Big)
There exists an easy construction to actually find triplets.
Construction
Select P = \displaystyle \text{min}\Big( \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor, \frac{|S|}{3}\Big) pairs, and add rest of the characters into a reserve. Now for each pair, pop out one character from reserve, and each pair along with popped character forms a valid pair.
Figure out why reserve contain sufficient characters.
Fun fact: Prove why printing |S|/3 gets accepted for first subtask.
Bonus: Does there exist a lower limit C such that the answer is always |S|/3 for fixed A = 26 and |S| \geq C
TIME COMPLEXITY
The time complexity is O(|S|+A) where A = 26
SOLUTIONS
Setter's Solution
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void solve() {
string s=readStringLn(1,100000);
vi cnt(256,0);
for(char i:s) {
assert('a'<=i&&i<='z');
cnt[i]++;
}
int sol=0;
for(int i:cnt)
sol+=i/2;
cout<<min(sz(s)/3,sol)<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(7);
int t=readIntLn(1,10);
// cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class THREE{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
String S = n();
int A = 26;
int[] f = new int[A];
for(int i = 0; i< S.length(); i++)f[S.charAt(i)-'a']++;
int count = 0;
for(int freq:f)count += freq/2;
pn(Math.min(count, S.length()/3));
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new THREE().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
VIDEO EDITORIAL (English):
VIDEO EDITORIAL (Hindi):
Feel free to share your approach. Suggestions are welcomed as always. 