Feb lunchtime 2021 div 3 question PALPAL

help
1

question: Palpal Strings | CodeChef
my solution: Solution: 43164811 | CodeChef
#include
#include <unordered_map>
using namespace std;

using namespace std;

int main()
{
int t;
cin>>t;
while(t–) {
string s;
cin>>s;
unordered_map<char, int> map;
for(int i = 0; i<s.length(); i++) {
map[s[i]] += 1;
}

    int ones = 0;
    int evens = 0;
    for(auto i : map ) {
        if(i.second == 1) ones++;
        if(i.second%2 == 0) evens++;
    }
    if(ones <= evens) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

return 0;

}

why is this wrong?
the question says
" * Each character of the whole string belongs to exactly one substring."
so why is my solution wrong?

2

Take a look at my solution. You will probably understand the logic.

3

@scisaif Actually your logic is correct. You are thinking in right way. Its just you missed one interesting point (I too got it later. Was making same mistake). If the frequency of number is greater than 2 (for even) and greater than 3(for odd). Than you can fit one count characters in it.
For eg.) S = “aaaabbbbbcde”
Substrings = ‘aca’, ‘ada’, ‘bbb’, ‘beb’
So, logic is to divide all even count by 2 and all (odd-3 (as you need 3 minimum characters for palindrome)) by 2. Total sum should be greater than 1 frequency character.

Hope you get it now :slight_smile:

1 Like
4

Just think here let’s say you have k once occuring characters then you need all of them to be handles by those which occur more than once so just count how much once occuring characters can be handled by others for example “aabbbbcfgdeeeee” can be written as acabfbbgbedeeee hence a handles 1 , b handles 2 and e handles 1 so we can make string palpal