Home » Python » Python programs

Python program to calculate the number of all possible substrings of a string

Here, we are going to learn how to calculate the number of all possible substrings of a string of length 1 to n using python program? By Sanjeev Last updated : February 13, 2024

Problem statement

Given a string and we have to calculate the number of all possible substrings of length 1 to n.

Solution approaches

This can be done by two ways:

1. By General Method

In this method, we first calculate all the possible substring by using nested for loops. After that count all the substring that we calculated. But this process is time-consuming and takes a lot of time if the length of the string exceeds too much.

Time Complexity : O(n*n) , n is the length of the string

2. By Formula

In this method, we can simply calculate the total number of possible substrings by a formula.

Total number of substrings:

    n + (n-1) + (n-2) + ... + 3 + 2 + 1
    = n * (n + 1) / 2

Time Complexity : O(1), ... Constant order

Note: It is not recommended that one should calculate the number of substring by General method because for larger strings system may become non-responsive. So use the formula to calculate the number of substrings.

Python code to count number of substrings of a string

def count_substr_by_formula(string):
    '''
    This function is used to calculate
    number of all possible substring of
    a string by a formula.
    '''

    substring = 0
    # length of the given string
    n = len(string)

    substring = n * (n + 1) // 2

    return substring

    # Time Complexity : O(1) {constant order}

def general_method(string):
    '''
    This function is used to calculate
    number of all possible substring of
    a string by using nested for loops.
    '''
    
    substring = 0
    n = len(string)
    # List to store all the calculated substrings
    substr = []

    for i in range(n):
        for j in range(i,n):
            substr.append(string[i:j])

    substring = len(substr)

    return substring

    # Time Complexity : O(n*n)

# Main Code
if __name__=='__main__':

    string = 'IncludeHelp'

    print('Total number of substring = %d' % count_substr_by_formula(string))
    print('Total number of substring = %d' % general_method(string))

Output

The output of the above program is:

Total number of substring = 66
Total number of substring = 66

Python String Programs »

To understand the above program, you should have the basic knowledge of the following Python topics: