Time limit exceeded error when using strlen()?

Question

The following code works as expected, this code prints the character that occurs the most number of times in a string:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    long int i,a[26]={0},m=0 ,c=0 ;
    char s[1000001] ;
    scanf("%s",s);
    for (i=0;s[i]!='\0';i++){
        a[s[i]-'a']++;
    }
    for ( i=0 ; i<26 ; i++)
        {
            if ( a[i] > m ) {       
            m = a[i] ;
            c = i ;
            }
        }

    printf("%c",'a' + c);
    return 0;
}

but when I use strlen() it causes a time limit error:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    long int i,a[26]={0},m=0 ,c=0 ;
    char s[1000001] ;
    scanf("%s",s);
    for (i=0;i<strlen(s);i++){
        a[s[i]-'a']++;
    }
    for ( i=0 ; i<26 ; i++)
        {
            if ( a[i] > m ) {       
            m = a[i] ;
            c = i ;
            }
        }

    printf("%c",'a' + c);
    return 0;
}

Where is the problem?

Did you try to execute the strlen outside the for loop? Like site_t len = strlen(s) ? I think that it may be overriding something. — prmottajr, Jun 30 '15 at 21:35
Does your string contain digits, punctuation, or special characters? This seems unlikely, but subtracting `'a'` does make assumptions so that the index for `a` does not go negative. When that happens, results are unpredictable. — donjuedo, Jun 30 '15 at 21:39
Also, any change you have a debug library for `strlen()`? That could incur quite a bit of overhead. — donjuedo, Jun 30 '15 at 21:40
strlen is quite slow as it is forced to linearly scan the string to find the ending `\0`. Try as @prmottajr suggests, use strlen once before the for loop. — fvu, Jun 30 '15 at 21:40
what happens when s[i] is not a lower case, printable, character? — user3629249, Jun 30 '15 at 22:17
Your use of `strlen` is inefficient -- but what is a "time limit error"? There are no restrictions in C on the execution time of a program. Are you running it in some environment that imposes such a restriction? Can you elaborate on that (preferably in the question)? — Keith Thompson, Jun 30 '15 at 22:18
regarding this line: 'scanf("%s",s);' 1) always check the returned code (not the parameter value) to assure the operation was successful. 2) while that input buffer 's[]' is quite large, it is still possible for the user to overflow the buffer. suggest: 'scanf("%1000000s",s);' as this habit will pay large dividends in most programs in saved debug time. Overflowing the input buffer is undefined behaviour and can/will lead to a seg fault event — user3629249, Jun 30 '15 at 22:21
amongst other things, code should not use 'magic' numbers beyond 0 and 1. Therefore, strongly suggest that '26' be #define MAX_ALPHA_CHARS (26) Then use the #define'd name wherever '26' is currently in the code. A similar recommendation of the value '1000001' — user3629249, Jun 30 '15 at 22:25
@prmottajr i tried what you suggested and it's working fine thank you :) , @ Keith Thompson, it was during a contest and the time limit per test is 2 second !, and thanks everyone for your answers :) — imadhsissou, Jun 30 '15 at 23:00
@imad2px: The "@" has to be immediately followed by the name for the person to be notified. — Keith Thompson, Jun 30 '15 at 23:02

Mr. Perfectionist · Answer 1 · 2015-06-30T23:09:03.473

2

for (i=0;i<strlen(s);i++)

This code is calling strlen(s) function. It takes O(n) time complexity.

for (i=0;s[i]!='\0';i++)

This code calls no functions, so will be much quicker than the previous.

In first, checks length of s in every iteration of i and it takes O(n) to find the last 0, so it takes O(n^2), the second case is O(n).

Here, O(n^2) is a very large for calculation.

edited Jun 30 '15 at 23:09

answered Jun 30 '15 at 22:51

Mr. Perfectionist

2,605
2
24
35

Function calls as such are not necessarily a problem, as they might be inlined (gcc for instance will heavily optimize many library functions using internal code). – too honest for this site Jun 30 '15 at 22:53
I think strlen is the problem for time limit. @Olaf. – Mr. Perfectionist Jun 30 '15 at 22:57
No kidding! Your answer, however implies it is just due to function calls, wheras it is because of the specifics of `strlen()`. – too honest for this site Jun 30 '15 at 23:01
Am I right now?? @Olaf – Mr. Perfectionist Jun 30 '15 at 23:10
I apparently cannot make my point clear. Perhaps, if you re-read my comments and think a little bit. The last edit, however, did not resolve anything. Just read this sentence of yours with open mind: "This code calls no functions, so will be much quicker than the previous." You actual expression is: "functions make code much slower." However, If I put the compare into a static function, the code most likely will not be a bit slower actually (unless compiled `-O0`), as the compiler will just inline the function without penalty. – too honest for this site Jun 30 '15 at 23:16
Got it. Thank you. @Olaf – Mr. Perfectionist Jun 30 '15 at 23:18

too honest for this site · Accepted Answer · 2015-06-30T23:19:03.463

char s[1000001]

Depending on OS, this might be too large for the stack. You should either allocate that dynamically using malloc() or at file-scope. Even if the stack is large enough, it is not good practice to have such large arrays on the stack.

Apart from that: strlen() is evaluated for each loop iteration, searching the string for the NUL terminator. For worst case (max. length), strlen is processed 1000000 times with searching all 1000001 positions of s (O(n**2)).

You should assign it to a variable outside the loop and use that to compare:

size_t slen = strlen(s);
for ( i = 0 ; i < slen ; i++ ) {

Or stick with the first version, that is fine, too.

Time limit exceeded error when using strlen()?

2 Answers2