2
\$\begingroup\$

This is the challenge I tried in Codefights: Avoid using built-in functions to solve this challenge. Implement them yourself, since this is what you would be asked to do during a real interview. Implement a function that takes two strings, s and x, as arguments and finds the first occurrence of the string x in s. The function should return an integer indicating the index in s of the first occurrence of x. If there are no occurrences of x in s, return -1. How can I make it faster? Thanks in advance. Here's my code, which is still slow for larger input cases(string of around 10^6 characters):

int findFirstSubstringOccurrence(String s, String x) { 
   int j=0;
   for (int i=0; i<=(s.length()-x.length()); i++) {
       j=0;
       while ((j<x.length()) && s.charAt(i+j)==x.charAt(j)){
           j++;
       }
       if (j == x.length()) 
           return i;
       if(s.charAt(i+j)!=s.charAt(i))
           i += j;
   }
   return -1;
}
\$\endgroup\$
1
\$\begingroup\$

Naming

findFirstSubstringOccurrence is quite a long name. substringIndex is shorter and still very explicit about what it does.


Your parameters are not named very well. When calling your method, how do you know which of the strings is the substring and which one the containing string? I suggest the method header int substringIndex(string containing, string candidate).

Style

Your use of white space is very unconventional. Usually you would have spaces around operators for example.


Using braces around one liners makes your code prettier and more readible, and also prevents bugs when you add a line without noticing the missing braces. Instead of this:

if(s.charAt(i+j)!=s.charAt(i))
    i += j;

write this:

if (s.charAt(i + j) != s.charAt(i)) {
    i += j;
}

Your initialization of j is redundant, since you assign 0 at the start of the loop anyway. So just declare it before the loop, then assign it in the loop.

Performance

Expecting the likely case that your string does not contain the substring candidate and returning early can improve your performance in many cases, so check before looping whether the candidate is longer than the containing string.


After finding the first occurence of the first letter of the candidate in the containing string, the next improvement would be to check whether the last letter of the candidate is at position firstLetterPosition + candidateLength - 1. That allows you to quickly find situations, where only a part of the substring is contained. Then you can check the middle part.

\$\endgroup\$
  • \$\begingroup\$ Thank you so much! The advice in the performance section was the one I was missing out on and I was failing with those larger cases! \$\endgroup\$ – Sanjiv Dec 22 '17 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.