ABC string WA!!

general
,
1

I have read the editorial before implementing this.But I don’t know what I’m missing:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
char s[1000002];
long int a[1000002],b[1000002],c[1000002];
typedef pair<long int,long int> key;
map<key,long long> mymap;
map<key,long long>::iterator it;
int main()
{
  long int i,n;
  long long ans;
  ans = 0;
  scanf("%s",&s);
  n = strlen(s);
  for(i=0;i<n;i++)
  { 
   a[i] = b[i] = c[i] = 0;
  }  
  for(i=0;i<n;i++)
  { 
   if(i != 0)
   {
    a[i] = a[i-1];
    b[i] = b[i-1];
    c[i] = c[i-1];
   }		
   if(s[i] == 'A')
    a[i]++;
   else if(s[i] == 'B')
    b[i]++;
   else
    c[i]++;
  }	   		
  key p1(0,0);
  mymap[p1]++;
  for(i=0;i<n;i++)
  {
   key p1(a[i]-b[i],a[i]-c[i]);
   mymap[p1]++;
  }  	     			
  for(it = mymap.begin();it != mymap.end();it++)
  {
   ans += it->second - 1;
  } 
  printf("%lld",ans);         
 return 0;
}
2

@hk02 : Try :

ans += ( it->second * (it->second - 1)) / 2;

Since every pair of such values corresponds to a different substring .

1 Like