Q:

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

belongs to collection: Python String Programs

mahmoud2506
Save to bookmark
|
2022-05-19
|
  216 
0

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
Python programming, examples, Python programming examples,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-19
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Python String Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Python program to reverse a given string (5 differ... >>
<< Python | Ignoring escape sequences in the string...