Expanding compressed string

I wrote this for a problem in one of the online contest at hackerearth. Problem statement is:


Input:



The first line contains the compressed string in form a2b4h5a2


Expanding it means aabbbbhhhhhaa.


You have to sort the expansion in increasing order(a-z). ie. aaaabbbbhhhhh


This is followed by Q that indicates the number of queries.


Follows Q lines each line contain an integer K.



Output:



For every question output the Kth character if it exists else print -1 .


It works correctly as intended, but help me make it faster as it exceeds time limit for that portal.
Any constructive criticism and advice is appreciated. :)

The idea is that, I made a integer array of size 26 to store the respective frequency of characters, thus sorting step is done automatically. Then just started subtracting the frequency value from the query until its zero or negative, that index is the required alphabet.

#include

int main() 
{

   // made a array to store frequency of alphabets 

    int ar[26] = {0};  
    int n=0, i=0, c=0, Q=0, K=0, m=0, chint=0;
    char str[10000];                   // use to store the compressed format string
    scanf("%10000[^\n]", str);

    for(i=0;str[i];i=i++)
    {
        if((str[i]>='a' && str[i]0)
            printf("-1\n");
    }

    return 0;
}

Warning

Enabling your compiler's warnings would tell you that c is unused.

Variable declarations

Following previous comments, I consider it good practice to declare your variable in the smallest possible scope and as late as possible. This makes things clearer (and prevent you from having unused variables). Using a "recent" version of C allows you to declare your variable in the for loop.

While/for

Your loop over Q is written as a while loop but could be written as a for loop.

i=i++

This is pretty weird code and according to my compiler warnings, might be undefined behavior.


expand.c:10:25: warning: operation on ‘i’ may be undefined [-Wsequence-point]

More about this here.

Ascii values

You are mixing literal characters (like 'a') that are easy to understand and ascii values (like '97') for no obvious reason. I'd rather have the literal characters used everywhere. It makes clearer the fact that we try to convert chars to indices in once case and to numbers in the other case.

Using temp variable

It would probably make sense to use a temporary variable for str[i] in order to make things clearer.

Variable names

The variable names you are using could probably be improved. Among other things m seems pretty cryptic to me.

Draft

At this stage, I have the following code:

#include

int main()
{
    int ar[26] = {0};
    char str[10000];
    scanf("%10000[^\n]", str);

    int last_char = 0;
    int nb_occ = 0;

    for(int i=0;str[i];i=i++)
    {
        int c = str[i];
        if((c>='a' && c0)
            printf("-1\n");
    }

    return 0;
}

Code organisation

On this kind of task, it is usually worth trying to split the input/output logic from the actual computing logic. Here, you could define 2 functions : one to initialise some object like structure from a string, one to use the structure to get the Kth character (K being the argument to the method).

This would allow you to write unit tests which would help you improve your algorithm.

Algorithm

You have used the correct ideas : use the proper data structure to store the different values used.

An improvement you could implement is to define a structure with the cumulated numbers that you compute once so that then you can get the kth element with a simple array lookup (actually as suggested by ChrisWue, maybe you'd need a binary search and not a single lookup). When multiple queries are performed (which is I think what is happening in your case), this should make things much faster.

The idea of doing some ("long") preprocessing once to make (multiple) queries much faster is a pretty classic solution in real life and in programming challenges.

StackExchange Code Review Q#119794, answer score: 4