In this HackerEarth Xsquare And Palindromes Insertion problem solution Xsquare likes strings a lot but much more, he likes palindromic strings. Today, he has a string S consisting of lower case English letters. Xsquare wants to convert his string S to a palindromic string. For the above purpose to be served, he can insert as many characters ( possibly zero ) as he wants in his string S such that characters in the new string S can be shuffled to make it a palindrome.

Xsquare is in hurry. Therefore, he wants to accomplish this task with the minimum possible number of insertions in his original string S.


HackerEarth Xsquare And Palindromes Insertion problem solution


HackerEarth Xsquare And Palindromes Insertion problem solution.

#include <bits/stdc++.h>
using namespace std ;
#define LL long long int
#define ft first
#define sd second
#define PII pair<int,int>
#define MAXN 100005
#define MAXM 10000001
#define mp make_pair
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
#define pr(x) printf("%d\n",x)
#define pb push_back
#define MOD 1000000007
#define MAX 1000010
#define ull long long
#define prime 37
#define pb push_back
#define ASST(x,y,z) assert(x >= y && x <= z)

int t , n;
string s ;
int main(){
    sc(t) ;
    ASST(t,1,100) ;
    while(t --){
        cin >> s ;
        n = s.length() ;
        ASST(n,1,1000) ;
        int M[26]={0} , c = 0;
        for(int i=0;i<n;i++) ASST(s[i],'a','z') ;
        for(int i=0;i<n;i++) M[s[i]-'a'] ++ ;
        for(int i=0;i<26;i++) if(M[i]&1) c ++ ;
        pr(max(0,c-1)) ;
    }
    return 0 ;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

int cnt[26];

int main()
{
    int t,n,ans;
    string s;
    cin >> t;
    while ( t-- ) {
        cin >> s;
        ans = 0;
        memset(cnt, 0, sizeof(cnt));
        int n = (int)s.size();
        for ( int i = 0; i < n; i++ ) cnt[s[i]-'a']++;
        for ( int i = 0; i < 26; i++ ) {
            ans += (cnt[i]%2);
        }
        ans--;
        ans = max(ans, 0);
        cout << ans << endl;
    }
    return 0;
}