How to reduce the execution time further?

Question

I'm trying a problem for a contest.The requirement is as below.

Problem:

Input_format:

Output_expected:

My C++ code is:-

#include <iostream>
using namespace std;

int main() {

long long n,i,j,k=0,p,q;
cin>>n;//takes size of string//
char s[n];
cin>>s;
cin>>p;//Number of test cases//
for(i=0;i<p;i++)
{
    cin>>q;//takes index to check till//
    for(j=0;j<q-1;j++)
    {
        if(s[j]==s[q-1])//checks if characters are equal//
        {
            k++;//if yes then counts it//
        }
    }
    cout<<k<<endl;
    k=0;//makes cout 0 for next iteration//
}

return 0;

}

So it seems the code works for most of the cases but there's this time constraint that seems exceeding for some cases.What more can be done to reduce the time.Thanks in advance for taking time to read this.

If you know the number of occurrences of every letter in the first `i` characters of the string, how can you figure out the number of occurrences of every letter in the first `i + 1` characters of the string? Do you have to iterate through the characters to count again? — eesiraed, Jul 13 '19 at 05:10
Your code has two errors, firstly `char s[n];` is not legal C++ because in C++ array bounds must be compile time constants, and `n` is a variable. Secondly even considering that, you need `char s[n+1];` because you need to have room for the nul terminator that ends every C string. — john, Jul 13 '19 at 05:16
@AlexanderZhang we can actually store the occurrences of all characters in one iteration by storing them in an array but in this case we still need a loop since there are p test_cases and each one has a different count. — Fiestyhokage, Jul 13 '19 at 05:17
Yes, in the end you will have an array that contains the counts for the entire string. However, you don't have to only look at the count array after the loop. Think about what the count array stores in each loop iteration. Doesn't it contain some useful information that you might want to store? — eesiraed, Jul 13 '19 at 05:22
@john do you think those errors are causing more execution time? — Fiestyhokage, Jul 13 '19 at 05:25
@Ananthhokage No, otherwise I'd have put them in an answer, not in a comment. What Alexander is getting is probably the solution. Your test runs don't have to be independent. — john, Jul 13 '19 at 05:25
The variable-length array only works because of a non-standard compiler extension. You shouldn't use it for the [same reasons that VLA's were removed in C++](https://stackoverflow.com/q/1887097/9254539). Besides, it makes your code non-portable, and allocating large arrays on the stack isn't a good idea. — eesiraed, Jul 13 '19 at 05:27
@AlexanderZhang so I should declare the array size statically with the large number right? — Fiestyhokage, Jul 13 '19 at 05:29
If you don't care about good practices and are only interested in competitive programming, I would recommend making all your arrays global with fixed sizes. If you want good practices, use `std::vector` or `std::string`. They dynamically allocate the array and manage the memory for you so you can have variable lengths without dealing with the memory allocation yourself. — eesiraed, Jul 13 '19 at 05:33
@Ananthhokage Let me lay it out for you (all credit to Alexander for this idea). Suppose you've done q=100 and s[100]='a' and you found the answer is 10. Now you're asked to do q=200 and s[200]='a' (also). Now you don't have to count from j=0, you already know that there are 10 'a's from 0 to 100, so you count from 100 to see how many more there are. That's the missing speed up. — john, Jul 13 '19 at 05:33
@john It actually gets simpler than that. I'll write an answer. — eesiraed, Jul 13 '19 at 05:33
Ananthhokage while you can get good advice here, when the code works as intended, but could be made to work better, a better site to use is [Code Review](https://codereview.stackexchange.com/help/asking). I've linked to their How to Ask pages because that's the best place to start any new adventure on the Stack Exchange. — user4581301, Jul 13 '19 at 05:34

eesiraed · Accepted Answer · 2019-07-13T05:55:26.470

Let's say we have an array cnt which stores the number of occurrences of each letter in the before the ith character of the string, for some i. We can easily update this array to include the ith character by simply incrementing the relevant element. So we'll iterate through the string updating this array, and at the ith iteration the cnt array will contain counts of every letter before index i.

Now, at the ith iteration, the information in the cnt array which would be useful for answering queries is cnt[s[i]], since that contains the number of occurrences of the character at index i in the part of the string preceding index i. We'll store this information in a[i], where a is some other array. So now a[i] is the number of occurrences of the letter at index i in all positions before i, which is exactly what we want for a query at index i. Therefore, we can now answer queries using the array.

Possible implementation:

#include <iostream>
#include <string>
#include <vector>

int main()
{
    //read input
    int n;
    std::string s;
    std::cin >> n >> s;
    //iterate through string maintaining cnt array and adding relevant values to array a
    int cnt[26] = { 0 };
    std::vector<int> a;
    a.reserve(n);
    for (int i = 0; i < n; i++)
    {
        int c = s[i] - 'a';
        a.push_back(cnt[c]);
        cnt[c]++;
    }
    //answer queries
    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++)
    {
        int p;
        std::cin >> p;
        p--;
        std::cout << a[p] << '\n';
    }
}

Oh dear Zhang! yes it works . Your awesome ,thanks for the algorithm man! — Fiestyhokage, Jul 13 '19 at 06:58
@Ananthhokage No problem. Make sure you understand how it works so that you can solve problems like these in the future. Don't just copy the code. For query problems like these, you'll almost always want to figure out a way to do some sort of preprocessing on the data to construct some data structure that will help you answer the queries. — eesiraed, Jul 13 '19 at 17:26
@Ananthhokage This isn't from an active contest, is it? I have reasons to believe it is. — eesiraed, Jul 13 '19 at 17:40

selbie · Answer 2 · 2019-07-13T05:50:48.713

First, this declaration:

long long n
cin>>n;//takes size of string//
char s[n];

Is non-standard. g++ supports it, but I don't believe variable sized arrays have made it into the C++ standard as it has for C. And I doubt you need long long as your index type unless you are scaling beyond 2 billion items.

Better:

int n;
cin>>n; //takes size of string
vector<char> s(n);

s is effectively the same as an array as for as accessing it at index locations with the [] operation.

Back to the solution:

Use a hash table that maps between a character and the number of occurrences of that character as you scan the s array once. Then use another array to keep track of how many times the character at that index was seen up to that point.

std::vector<int> positionCount(n);
std::unordered_map<char, int> table;

Insert your characters from s into the table and positionCount table as follows

for (int i = 0; i < n; i++)
{
    char c = s[i];

    // table[c] is the number of occurrences that "c" was seen in the input array so far
    table[c]++;

    // since table[c] is getting updated as we iterate, 
    // Keep track of the count of the char at position i in a separate array
    positionCount[i] = table[c];
};

Then for each test case:

for(i=0;i<p;i++)
{
    cin>>q; //takes index to check till

    q--; // off by 1 fix since the array is described as 1..N


    long result = positionCount[q];

    result--; // off by 1 fix again since the output is the preceeding count and doesn't include the character at position q.

    cout << result << endl;

}

All of the above is intuitively faster since there's no inner for loop. Hash table insertion and lookup is O(1) as is each array lookup.

And if you are into the whole brevity thing, you can simplify the above into this:

for (int i = 0; i < n; i++)
{
   positionTable[i] = table[s[i]]++;
}

for(i=0;i<p;i++)
{
   cin >> q;
   cout << positionTable[q-1] << endl;
}

How to reduce the execution time further?

2 Answers2