CHAAT6 - Editorial

PROBLEM LINK:

Contest

Author: Harshavardhini B
Tester: Hareesh V
Editorialist: Harshavardhini B

DIFFICULTY:

SIMPLE

PREREQUISITES:

Hashing

PROBLEM:

Given a string s and a set of queries where each query (l,r). For each query, find the number of super minimums in the substring s[l],s[l+1]…s[r]. Super-minimum is a character at a position i such that s[i]<s[i-1]. By default the first character in any string is a super-minimum.

EXPLANATION:

Brute force approach is iterate through the substring for each query and check for super-minimums. Time complexity for the above approach is O(n*q).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin>>s;
long long int ans,l,r,q;
cin>>q;

for(long long int i=0;i<q;i++)
{
    cin>>l>>r;
    long long int ans=1;
    for(long long int j=l+1;j<=r;j++)
    {
        if(s[j]<s[j-1])
        ans++;
    }
    cout<<ans<<"\n";
}
return 0;

}