HackerEarth A sorted string problem solution YASH PAL, 31 July 2024 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';} coding problems