CODEWITHSUNDEEP
cstring
toy
toy

Reputation: 12161

Why this C program to find the first unique character in a string is too slow?

I'm new to C. So, I'm trying to learn through leetcode.

https://leetcode.com/problems/first-unique-character-in-a-string/

This is the question

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode" return 0.

s = "loveleetcode", return 2.

And this is my code

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

int firstUniqChar(char* s) {
  int c = 0;
  int freq[26] = {0};

  while (s[c] != '\0') {
    if (s[c] >= 'a' && s[c] <= 'z') {
      freq[s[c] - 'a']++;
    }
    c++;
  }

  int firstChar = -1;
  for (int i = 0; i < strlen(s); i++) {
    if (freq[s[i] - 'a'] == 1) {
      firstChar = i;
      break;
    }
  }
  return firstChar;
}

I can't prove that my code is correct since it said Time limit exceeded. So, I'm guessing my program is too slow. Not sure where did I do it wrong?

Upvotes: 1

Views: 602

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58339

Your code is accidentally O(n^2) because strlen(s) takes O(n) time, and is executed on each iteration of the second loop. As in the first loop, you can iterate until you find a \0 character:

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

On correctness: your first loop only counts characters if they are in the range a-z but your second loop doesn't. That means either that the checks are redundant in the first loop, or the second loop is wrong (because it will access freq out of range if there's a character that's not in the range a-z in s).

Upvotes: 3

Related Questions