# HackerEarth A sorted string problem solution

In this HackerEarth A sorted string problem solution You are given a string S of length N. The string contains only 'a', 'b', and 'c'.

Your task is to find the count of substrings in string S that have F('a') > F('c'). Print ans%(10^9 + 7).

Here, F(x) denotes the frequency of occurrence of character x in the string.

## HackerEarth A sorted string problem solution.

`#include<bits/stdc++.h>using namespace std;#define int long longint BIT[800000];int query(int x)      //returns the sum of first x elements in given array a[]{     int sum = 0;     for(; x > 0; x -= x&-x)         sum += BIT[x];     return sum;}void update(int x, int delta)       //add "delta" at index "x"{    for(; x <= 3e5; x += x&-x)          BIT[x] += delta;}int solve(string s, int n){    memset(BIT, 0, sizeof(BIT));    // make binary    int com[n+1] = {0};    for(int i=0;i<n;i++)    {           int flag = (s[i]=='a'?1:(s[i]=='b'?0:-1));        com[i+1] = com[i] + flag;    }        // compress BIT    map< pair<int,int>, int > dup;    for(int i=0;i<=n;i++)    dup[{com[i], i}] = 0;        int i=1, prev = 0;    for(auto it = dup.begin(); it != dup.end(); it++)    {        if(it->first.first != prev)            i++;        it->second = i;        prev = it->first.first;        // cout << it->first.first << " " << it->first.second << " " << it->second << "\n";    }    // cout << i << "\n";        update(dup[{0,0}], 1);    // BIT calls    int ans = 0;    for(i=1;i<=n;i++)    {        int z = query(dup[{com[i], i}]-1);        ans += z;        // cout << z << " ";        update(dup[{com[i], i}], 1);    }    return ans;}int32_t main(){    int n;    string s;    cin >> n >> s;        cout << solve(s, n);    return 0;}`

### Second solution

`#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>using namespace std;using namespace __gnu_pbds;template<typename T>struct MOS{    tree<pair<T, int>, null_type, less<pair<T, int>>, rb_tree_tag,tree_order_statistics_node_update> os;    map<T, int> cnt;    int size(){        return os.size();    }    int order_of_key(const T &x){        return os.order_of_key({x, 0});    }    int ge(int x){        return os.size() - order_of_key(x);    }    void insert(const T &x){        os.insert({x, cnt[x]++});    }    void erase(const T &x){        os.erase({x, --cnt[x]});    }};typedef long long ll;const int maxn = 1e3 + 14, mod = 1e9 + 7;int main(){    ios::sync_with_stdio(0), cin.tie(0);    MOS<int> os;    int n;    cin >> n;    string s;    cin >> s;    int cur = 0;    os.insert(cur);    ll ans = 0;    for(auto c : s){        if(c == 'a')            cur++;        else if(c == 'c')            cur--;        ans += os.order_of_key(cur);        os.insert(cur);    }    cout << ans % mod << '\n';}`