HackerEarth Chandan and Balanced Strings problem solution

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.

#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("%lldn",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;
}

HackerEarth Chandan and Balanced Strings problem solution.

Second solution

Leave a Reply