# PROBLEM LINK:

Author: Jeevan Jyot Singh
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

Simple

None

# PROBLEM:

You are given a string S (consisting of lowercase Latin letters only) and you can rearrange the letters of this string in any way. You have to find out if it is possible to rearrange the letters of string S to obtain a Palpal string.

A string S (consisting of lowercase Latin letters only) is called a Palpal string if it can be divided into contiguous substrings such that:

• Every Character of the string is present in one and only one substring.
• Every Substring is a palindrome of length \ge 2

# EXPLANATION:

Our task is to divide the string into contiguous substring of length greater than or equal to two, such that every substring is a palindrome.

If there is a palindromic substring and we delete the leftmost and the rightmost character from this substring, the resulting substring will remain palindromic. It means to create a palindromic substring of length x, we need to create a palindromic substring of a smaller length too. Hence the most optimal way to divide the string is in the smallest length possible which is 2.

Dividing the string S into substrings of length 2 will also increase palindromic substrings which will be useful when we need to insert the odd character in these substrings as explained later.

Now we will try to form palindromic substrings of length 2. We can see that, if any letter is present an odd number of times in this string then a single character of this letter wonât be able to form a palindromic substring of length 2. But all such characters can be inserted in between substring of length 2 since the addition of this character wonât make the substring non-palindromic. It means that there should be enough substrings such that all such characters could be inserted.

Let us suppose the count of such characters is y. Now if the number of substrings of length 2 is more than or equal to y, then it is always possible to insert such characters in between the substrings making the substring still palindromic. If such conditions satisfy then it is possible to rearrange the letters of string S to obtain a Palpal string.

# TIME COMPLEXITY:

O(|S|) per test case.

# SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int32_t main()
{
IOS;
int T; cin >> T;
while(T--)
{
string s; cin >> s;
int single = 0, pair = 0;
vector<int> freq(26);
for(int i = 0; i < (int)s.size(); i++)
freq[s[i] - 'a']++;
for(int i = 0; i < 26; i++)
{
pair += freq[i] / 2;
single += freq[i] % 2;
}
if(single <= pair)
cout << "yeS";
else
cout << "No";
cout << "\n";
}
return 0;
}
Tester
#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,' ');
}

int sum_s=0;
void solve() {
string s=readStringLn(1,100);
sum_s+=sz(s);
assert(sum_s<=1000'000);
for(char i:s)
assert('a'<=i&&i<='z');
vi cnt(26,0);
for(char i:s)
cnt[i-'a']++;
int ones=0,eves=0;
for(int i:cnt)
if(i) {
ones+=i%2;
eves+=i/2;
}
if(ones>eves) {
cout<<"NO"<<endl;
} else
cout<<"YES"<<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(10);
int t=readIntLn(1,100000);
//	int t;
//	cin>>t;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

Editorialist
#include<bits/stdc++.h>
using namespace std;

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
{
string s;
cin>>s;

int n=(int)(s.size());

int count[26]={};

for(int i=0;i<(int)s.size();i++)
{
count[s[i]-'a']++;
}

int odd=0;

for(int i=0;i<26;i++)
{
if(count[i]%2!=0)
{
odd++;
}
}

int total=n-odd;
total/=2;

if(total<odd)
{
cout<<"NO"<<"\n";
}
else
{
cout<<"YES"<<"\n";
}
}

return 0;
}

# VIDEO EDITORIAL:

3 Likes

Am I the only one who misunderstood the statement âEvery Character of the string is present in one and only one substringâ as âEvery letter of the string appears in one and only one substringâ ?

37 Likes

Definitively not alone. I read that multiple times to get the clear view.

4 Likes
#include <bits/stdc++.h>
#define ll  int
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
string s;
cin>>s;
map<char , int>mp;
for(int i =0;i<s.size();i++){
mp[s[i]]++;
}

int e =0 , o = 0 , tot = 0 , so=0 , tot1 = 0;

for(auto x : mp){

if(x.second%2==0)
{
e++;
tot+=x.second;
}
else if(x.second == 1){
so++;
}
else{
o++;
tot1+=x.second;
}

}
if(so==0){
cout<<"YES"<<endl;
}
else if(so>0 and tot > 0 ){
if(tot%so==0 and tot!=so){
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
}
else
cout<<"NO"<<endl;

}
return 0;
}

my solution is failing for which test case?

1 Like

A string SS (consisting of lowercase Latin letters only) is called a Palpal string if it can be divided into contiguous substrings such that:
how answer is true for âabaâ if it can not be divided any further

Can anyone help me out that where I missed?. I was trying to consider characters with odd frequency count(!=1) as a single substring so I was not counting them but the solutions which are accepted are also considering the strings with odd length(!=1). It would be a great help if you can show me an example for my mistake and which statement of the question I read wrong?
Thanks in advance!

1 Like

âabaâ in iteself is a palindrome and it is a substring of âabaâ

1 Like

Why am I getting wrong answer? I am not getting it âŚ Plz Help

t=int(input())
for i in range(t):
s=input()
count=0
eve=0
res = {i : s.count(i) for i in set(s)}
for value in res.values():
if(value==1):
count+=1
elif(value%2==0):
eve+=1
if(len(s)==1):
eve=1
count=2
if(eve>=count):
print(âYESâ)
else:
print(âNOâ)

1 Like

A string is called a Palpal string if it can be divided into contiguous substrings such that:

Each character of the whole string belongs to exactly one substring.
Each of these substrings is a palindrome with length greater than 1

How âaaâ is a palpal string ??It cannot be divided into substring with length>1

1 Like

I am unable to understand yetâŚ
âadddddâ should give NO
but it is giving YES according to their solutionâŚ
âdâ canât be present in 2 substring,right?

2 Likes

Bro the problem is that you are not considering the case when the characters appearing once can be made to form palindrome with those which appear more than one and for any character which appear even number of times letâs say cnt it can handle cnt/2 characters appearing once and the character which appear odd number of times say cnt and greater than 3 can handle (cnt-3)/2 characters appearing once
for example xxyyddddddgggggefhkli can be arranged as xexyfydhddkddldgigggg
here 6 ds handle 6/2 = 3 characters which appear once and 5 gs handle one character (5-3)/2 = 1 which appear once , hope it make sense CodeChef: Practical coding for everyone

1 Like

Can anyone tell me where is my code failing ??? I have counted single time occurring characters and trying it to fit into even freq characters. (basically calculating the difference of even and single freq count ). I think I missed something in the problem statementâŚ

int main()
{

ll t;
cin>>t;

while(t--)
{
string s;
ll count=0,even=0;
cin>>s;
ll f[26];
for(int i=0;i<26;i++)
{
f[i]=0;
}

for(ll i=0;i<s.size();i++)
{

f[s[i]-'a']++;

}

for(int i=0;i<26;i++)
{
if(f[i]==1)
{
count++;
}
if(f[i]%2==0 && f[i]>1)
{
even++;

}

}

if(even<count)
{
cout<<"NO"<<endl;

}

else{
cout<<"YES"<<endl;
}

}

}

A single substring of length > 1 is valid as well. Probably would have been clearer as âdivided into one or more contiguous substringsâ or âdivided into contiguous substring(s)â or some wording like that.

2 Likes

basically in this question we had to divide characters with length 2 in first part and characters with length 1 in second part and just check if characters with length 2 are greater or equal to characters with length 1 then answer is yes else no

for eg : ghxxxyyzz
characters with length 2 : xx yy zz
characters with length 1 : g h x
result : xgx yhy zxz

am I right @cherry0697 ?

aa itself is a substring

but you also need the count how many single character each character which occurs more than once can handle for example in addddb the even occuring character d can handle a as well as b as daddbd similiarily hence the even occuring character letâs say it occurs x times can handle x/2 single occuring ones and the odd occuring character letâs say y times it occur can handle (y-3)/2 single occuring chars.CodeChef: Practical coding for everyone

1 Like

1
bbbccddeeffghi
Your Output :No
Answer is :
Yes
Possible string:
bbbcgcdhdeieff

every one is getting confused by the problem statement the ones who did by counting the frequency of character which appeared only once.
I think the problem statement was not clear. At first i also thought that
every sub-string must have a unique character after reading the problem statement

2 Likes

so thats why merging all the characters together and then giving characters with frequency 1 to characters with odd frequency greater than 1

Bro, In the question It said
âEach character of the whole string belongs to exactly one substring.â

suppose âdadâ,âdddâ be the two subtrings. and the string can be like âdaddddâ.
which means
0 th index is in substring 1
1 st index is in substring 1
.
.
.

That means Every index is uniquely getting into either substring 1 or substring 2.

In question it is trying to explain

There cannot be a character in string that is in more than 1 substring, Repeated caharcters will contribute to some other string.

Hope this helps.
Happy Coding : )

3 Likes