ABC-String

Dear all ,
I am getting WA for the below solution .While local testing , I am getting correct Answer .

Any pointer will help me to understand the issue in below implementation

Thanks
rajesh

############
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#define STRING_LENGTH 1000005
char data[STRING_LENGTH];
using namespace std;
vector<pair<long,long> >v(STRING_LENGTH);
int main()
{
  freopen("input.txt","r",stdin);
   memset(data,'\0',STRING_LENGTH);
   cin >> data;
    long d1 = 0;
    long d2 = 0;
   unsigned long i = 0;
    v[0].first = 0;
	v[0].second = 0;
   while(data[i] != '\0')
   {
	   if (data[i] == 'A')
	   {
		   d1++;
	   }
	   else if (data[i] == 'B')
	   {
		   d2++;
	   }
	   else if ( data[i] == 'C')
	   {
		   d1--;
		   d2--;
	   }
	   v[i+1] = make_pair(d1,d2);
	   i++;
   }
   sort(v.begin(),v.begin()+i+1);
   unsigned long index = i;
    long a = -1;
    long b = -1;
   unsigned long counter = 0;
   unsigned long sum = 0;
   i = 0;
   while(i <= index )
   {
	   if (v[i].first == a && v[i].second == b)
	   {
		   counter++;
	   }
	   else
	   {
		   sum += ((counter)*(counter-1))/2;
		   counter = 1;
		   a = v[i].first;
	       b = v[i].second;
	   }
	   
	   i++;
   }
   sum += ((counter)*(counter-1))/2;
   cout<<sum<<endl;
   v.clear();
   sum = 0;

   return 0;
}


###########

You have understood the question incorrectly. There should be equal no of A’s , B’s and C’s in the substring doesn’t mean there should be exactly 1-A, 1-B and 1-C in the substring. E.g.

For String abcabc

The answer should be 3 as {abc},{abc} and {abcabc}.

1 Like