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("%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;
}
0 Comments