How to solve "A Sorted String" problem from Hackerearth

I am trying to solve A Sorted String from Hackerearth.

I am solving it using BIT, but eventually i was unable to get the actual idea.
I saw the solution of some guy who has solved this question with less code.
I am unable to understand his approach.
Could anyone help me in solving this question.
Thank you :slight_smile:

@everule1
CODE : https://www.hackerearth.com/challenges/competitive/data-structures-and-algorithms-coding-contest-july-2020/algorithm/sorted-string-3-a95dada3/submission/44140940/

1 Like

My guess is he mapped a to 1, b to 0, and c to -1. Now for count of a to be larger than count of c, you’re looking for the number of subarrays that have a total sum greater than 0. Now just calculate the prefix sums, and each subarray can be represented as the difference between a pair of prefix sums. For each index he is counting how many previous prefix sums have a value less than the current prefix sum. If a prefix sum has value k, then he is adding 1 from k to n that there is a new value less than this.

Also Shorter code


#include <iostream>
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using indexed_set = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;  
const int p= 1e9 + 7;
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> prefixsum(n+1);
    for(int i=1;i<=n;i++){
        prefixsum[i] = prefixsum[i-1];
        if(s[i-1] == 'a'){
            prefixsum[i]++;
        }
        else if(s[i-1] == 'c'){
            prefixsum[i]--;
        }
    }
    indexed_set curr;
    ll ans = 0;
    for(int i=0;i<=n;i++){
        ans+=curr.order_of_key(prefixsum[i]);
        curr.insert(prefixsum[i]);
    }
    cout<<ans%p<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
2 Likes

Thanks a lot :slight_smile: