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
@everule1
CODE : Log In | HackerEarth
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