jeudi 28 mai 2020

Reducing the time complexity of the program

I am doing this practice problem where given a string s of lowercase letters, and a position p, I have to print all the occurrences of the letter at position p which occur before the position p.

Eg: If the string is "abaac" and p=3(1 based index) then output is 1 because 'a' occurs one time before the position p.

There are q queries each giving me a position p. Is there any way to make this code more efficient?
I'm using hashing which is pretty efficient I think? Is there any algorithm that I am not aware of?

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int q;
    cin>>q;
    while(q--)
    {
        int p;
        cin>>p;
        int freq[26] = {0};
        for(int i = 0; i<(p-1); i++)
            freq[s[i]-'a']++;
        cout<<freq[s[p-1]-'a']<<"\n";
    }

}

Aucun commentaire:

Enregistrer un commentaire