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?
Submitted by Sanjeev, on April 11, 2019

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

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

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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL







Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.