Count overlapping substrings in a given string in Python

In this tutorial,  we will learn to count the number of overlapping substrings in a given string in Python.

First, let’s try to understand the problem statement.

Let us assume we have a string: “codespeedycodespeedy”. In the given string, the number of occurrences of the substring “codespeedy” is 2. But if you take your string to be “thathatthat”, the count of the number of the overlapping substrings “that” is 3.

Now let us see how to get this task done.

How to count overlapping substrings in a given string in Python

Python has some inbuilt functions which perform specific tasks.

string.count(sub-string) is an inbuilt function that counts the occurrences of a substring in the given string.

Let us see if this works.

def overlapCount(string, substr):
    count = string.count(substr)
    return count

print("The count is: ", overlapCount("thatthathat","that"))

Output:
The count is: 2

Do you think this is what we want?

No, it does not count the overlapping strings. For this, we need to write our own function definition.

Let us understand this by code.

def frequencyCount(string, substr):
   count = 0
   pos = 0
   while(True):
       pos = string.find(substr , pos)
       if pos > -1:
           count = count + 1
           pos += 1
       else:
           break
   return count

print("The count is: ", frequencyCount("thatthathat","that"))

Output:
The count is: 3

• string.find(sub-string, start, end) returns the starting index of the sub-string in the range of (start, end).
• If the substring doesn’t exist, it returns -1.

Now in the code, we keep a count variable to store the count and pos to track the starting index of the sub-string. When the sub-string is encountered, increment the counter and check from the next index.

This is how we calculate the overlapping substrings.

Also read:

• How to shuffle a word in Python
• Modular multiplicative inverse in Python