In this HackerEarth Chandan and Balanced Strings problem solution, Chandan got bored playing with the arrays all the time. Therefore he has decided to buy a string S consists of N lower case alphabets. Once he purchased the string, He starts formulating his own terminologies over his string S. Chandan calls a string str A Balanced String if and only if the characters of the string str can be partitioned into two multisets M1 and M2 such that M1= M2.


HackerEarth Chandan and Balanced Strings problem solution


HackerEarth Chandan and Balanced Strings problem solution.

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

#define MAXN 100010
#define LL long long int 


int T,N;
char str[MAXN] ;
vector<int> A ;

int main(){

    scanf("%d",&T) ;
    assert(T >= 1 && T <= 100000) ;
    while(T--){
        scanf("%s",str+1) ;
        N = strlen(str+1) ;
        assert(N >= 1 && N <= 100000) ;
        int val = 0 ;
        A.push_back(val) ;
        for(int i=N ; i >= 1 ; i--){
            int bit = str[i]-'a' ;
            val = val ^ (1 << bit) ;
            A.push_back(val) ;  
        }
        sort(A.begin(),A.end()) ;
        int i = 0;
        LL ans = 0;     
        while(i<=N){
            val = A[i] ;
            LL cnt = 0;
            while(i<=N && val == A[i]){
                cnt ++ ;
                i ++ ;
            }
            ans = ans + (cnt*(cnt-1))/2 ;
        }
        printf("%lld\n",ans) ;
        A.clear() ;
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

int dp[100005];

int main()
{
    int t,n;
    long long ans;
    string s;
    map <int,long long> m;
    cin >> t;
    while ( t-- ) {
        cin >> s;
        n = (int)s.size();
        assert(n<=100000);
        m.clear();
        dp[0] = 0;
        ans = 0;
        for ( int i = 1; i <= n; i++ ) dp[i] = dp[i-1]^(1<<(s[i-1]-97));
        m[dp[0]]++;
        for ( int i = 1; i <= n; i++ ) {
            ans += m[dp[i]];
            m[dp[i]]++;
        }
        cout << ans << endl;
    }
    return 0;
}