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.
#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;
}
0 Comments