In this HackerEarth Beautiful Strings problem solution, A string is beautiful if it has equal number of a,b,and c in it.
Example "abc" , "aabbcc" , "dabc" , "" are beautiful.
Given a string of alphabets containing only lowercas aplhabets (a-z), output the number of non-empty beautiful substring of the given string.


HackerEarth Beautiful Strings problem solution


HackerEarth Beautiful Strings problem solution.

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define CLR(a) a.clear()
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define FORi(i,a,b) for(LET(i,a) ; i<b; i++)
#define repi(i,n) FORi(i,(__typeof(n))0,n)
#define FOR(i,a,b) for(i=a ; i<b; i++)
#define rep(i,n) FOR(i,0,n)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pi(n) printf("%d",n)
#define piw(n) printf("%d ",n)
#define pin(n) printf("%d\n",n)
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;
string s;
PII a[100001];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>s;
n = SZ(s);
a[0].F = a[0].S = 0;
repi(i,n)
{
a[i+1]=a[i];
if(s[i]=='a'){a[i+1].F--;a[i+1].S--;}
if(s[i]=='b')a[i+1].F++;
if(s[i]=='c')a[i+1].S++;
}
n++;
sort(a,a+n);
LL ans=0;
LL c = 1;
for(int i = 1; i < n; i++)
if(a[i]==a[i-1])
c++;
else
{
ans += (c*(c-1))/2;
c=1;
}
cout<<ans<<endl;
}
return 0;

}

Second solution

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define CLR(a) a.clear()
#define SET(a,b) memset(a,b,sizeof(a))
#define TR(v,it) for( typeof(v.begin()) it(v.begin()) ; it != v.end() ; it++)
#define FOR(i,a,b) for(i=(int)a;i<(int)b;i++)
#define si(n) scanf("%d",&n)
#define rep(i,n) FOR(i,0,n)
#define repi(i,n) for(int i=0; i<n; i++)


using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;
LL power(LL a, LL p)
{
LL ret=1;
while(p)
{
if(p&1) ret = (ret*a);
p/=2;
a = (a*a);
}
return ret;
}
LL gcd(LL a, LL b)
{if(b) return gcd(b,a%b); return a;}
PII A[1000001];
int main()
{
int t;
scanf("%d",&t);
while(t--){

A[0] = MP(0,0);
string s; cin>>s; int n = SZ(s);
repi(i,n)
{
A[i+1] = A[i];
if(s[i]=='a')
A[i+1].F++;
if(s[i]=='b')
{
A[i+1].F--;
A[i+1].S++;
}
if(s[i]=='c') A[i+1].S--;

}
sort(A,A+n+1);
LL ans=0;
LL c=1;
for(int i=1; i<=n;i++)
{
if(A[i]==A[i-1])c++;
else
{
ans += (c*(c-1)) / 2;
c=1;
}
}
ans += (c*(c-1))/2;
cout<<ans<<endl;
}
return 0;
}