A Counting Problem

I really love sites like Hackerrank and their programming challenges. Lately, one of them took my attention given that the simplest and standard solution didn´t work. The challenge is named “Find a String” and the idea is really simple: Count substring occurrences inside a string.

My first impression was the obvious one: “Hey, Python have this implemented”, so I tried the count method. This counts the number of times a sub string appears in a string, it is used like this:

string.count(substring)

But, the program failed. Look at this (there was another restriction, strings should have less or equal 200 characters):

def count_substring(string_to_eval, substring):
     if len(string_to_eval)<201:
          return string_to_eval.count(substring)
     else:
          return 0

strint_to_eval = "ABCDCDC"
substring = "CDC"
print(count_substring(strint_to_eval,substring))

If you run this, the result is 1 but the expected result is obviously 2.

My second thought was using regex library, something like this:

 

import re
def count_substring(string_to_eval, substring):
    if len(string_to_eval)<201:
        return len(re.findall(substring, string_to_eval))
    else:
        return 0

strint_to_eval = "ABCDCDC"
substring = "CDC"
print(count_substring(strint_to_eval,substring))

But again, the result was 1.

So, times like this is when you have to stop thinking in default language methods and libraries and start thinking in algorithmic solutions.

Here is something that happens to me when something standard is not doing what I want: I do things like a craftsman, so this is a quick approach of the function:

def count_substring(string_to_eval, substring):
    counter = 0
    if len(string_to_eval)<201:
        i=0
        while i<len(string_to_eval)-len(substring)+1:
            is_equal=True
            k = i
            for j in substring:
                if j!=string_to_eval[k]:
                    is_equal=False
                k += 1
            if is_equal==True:
                counter = counter+1
            i= i+1

        return counter
    else:
        return 0

This might overkill the problem and there are many improvements in the code that can be done to make it faster, but for now, this would work.

So, the lesson is: always test your code, maybe some things that you think are OK because you are using the language standards can fail.

Leave a Reply

Your email address will not be published. Required fields are marked *