you need to count total pairs which can be made, so that you can fit those characters inside it which occur only once. So basically you need to maximise the pairs.
in your code you are considering that all even numbers can make only one pair but 4 can make 2 , 6 can make 3 pairs.
similarly you need to count pairs for those elements also whose occurence is odd . suppose an element occurs 7 times so you can take 4 elements from this and make 2 pairs out of it and let the remaining 3 elements make the pallindrome.
in this way count total possible pairs and total no of elements which occurs only once. and then check if pairs are more than the elements occuring only once so that they can fit all of them to make the pallindrome.
Each character of the whole string belongs to exactly one substring.*
and in the example it says xyxyxy is valid because xyx and yxy
but doesn’t this contradict the above statement?
I Got WA because of this statement, not fair.
Could someone please tell where is my code failing?
#include<bits/stdc++.h>
using namespace std;
long int t;
int main()
{
cin>>t;
while(t--)
{
string s;
std::vector<int> v;
int count,one=0,even=0;
cin>>s;
for (int i = 0;'a'+ i <='z'; ++i)
{
count=0;
for (int j= 0; j<s.length(); ++j)
{
if (s[j]=='a'+i)
{
count++;
}
}
if (count!=0)
{
v.push_back(count);
}
}
for (int i = 0; i <v.size(); ++i)
{
if (v[i]==1)
{
one++;
}
if (v[i]%2==0)
{
even++;
}
}
even>=one ? cout<<"YES"<<endl : cout<<"NO"<<endl;
}
return 0;
}
Can someone explain this line " Every Character of the string is present in one and only one substring?" .Does this mean that every string must contain unique characters ??? Like abc def ghi is valid and abc ceb is not valid as c and b is repeating in both.???
I had done the same but later read the question carefully, and then I realized that same character(by same i mean the value) can occur in two different substrings.
example : given string : addddd
substring 1: dad
substring 2: ddd
the statement was little bit confusing which costed me my time
Even they are odd if their count is >= 5 (ex: “aaaaa”) you can divide them further such as “aaa” and “aa” and the even part should be added to the number of evens so it can used to turn one of the single characters into palindrome if needed. if count for odd is n then you should add (n-3)//2 to your evens.
WA.My approach was to put all the characters of frequency = 1 between 2 (same) characters . For example : aab will become aba. If Any character with an odd frequency they can be formed independently as they can form a palindrome. but the frequency of even characters must be considered for placing the character with frequency = 1.
for example : acbbbadzdz will be aca|bbb|dd|zz
for a better understanding plz see my code: CodeChef: Practical coding for everyone
can someone please help what is wrong in this approach or did i just misunderstand the question?
You are missing some cases.
If there are aaaabc it should print yes bcoz it can be break in aba, aca.
And aaaaaaabc should also print yes
It can be break in aba, aca, aaa
