c - Finding substring with equal number of characters -

for problem need find number of substrings of string number of repetitions of each character should same. given string consists of 3 characters(a,b,c).

i make algo of o(n^2).

for(;i<len;i++) {  if(s[i]=='a')  ac++;  else if(s[i]=='b')  bc++;  else if(s[i]=='c')  cc++;  for(k=i+1;k<len;k++)  {   if(s[k]=='a')   ac++;   else if(s[k]=='b')   bc++;   else if(s[k]=='c')   cc++;   if(ac==bc && bc==cc)   {count++;}  }  ac=0;bc=0;cc=0; } 

it takes long time calculate longer strings(for in range of 10^5). please in getting better solution.

if willing implement hash map in c, can solve in believe o(n).

keep normalised count of , bs. normalised mean c count in zero. c count implied, because string contains as, bs , cs , current string length must therefore + b + c.

start hash map count of 1 (0, 0) count.

pass through string once. when pass a, increment count. when pass b, increment b count. when pass c, decrement both , b counts. add current count (a, b) hash map if doesn't exist , increment it.

to illustrate:

        0   0       1   0  *-------------- b       1   1        valid       2   1        substring c       1   0  *--------------       2   0 

finally, loop on hash map entries , add triangle sum of entry overall count. triangle sum t(n), mean: t(1) = 0, t(2) = 1, t(3) = 2 + 1, t(4) = 3 + 2 + 1 , on. reflects fact hash entries represent borders of valid substrings , can merge adjacent substrings:

acb      abc      bca      bca       +4    acbabc   abcbca   bcabca          +3      acbabcbca   abcbcabca           +2          acbabcbcabca                +1 

in pseudo c:

int nsubseq(const char *str) {     map *map = map_new();     const char *p;      int aa = 0;     int bb = 0;      map_add(map, key(aa, bb), 1);      (p = str; *p; p++) {         if (*p == 'a') aa++;         else if (*p == 'b') bb++;         else if (*p == 'c') aa--, bb--;          int *q = map_find(map, key(aa, bb));         if (q) {             *q = *q + 1;         } else {             map_add(map, key(aa, bb), 1);         }     }      int count = 0;             (int *p = map_begin(map); p; p = map_next(map)) {         int n = *p;          while (n--) count += n;     }      map_delete(map);      return count; } 

(that's real c, have implement map functions. or use existing hash map implementation, of course.)

the performance of code depends on hash map implementation, hash size of 4096, can scan string of 1 million equally distributed as, bs , cs in less second. optmum case; performance goes down less evenly distributed string is. corner cases without hits (only or , bs), every character creates new entry in hash map, take twelve times longer.

if entries hash lists of indices instead of counts, extract values of substrings, although string 100k entries, overkill.