Count subsequence of length three in a given string | Function to find number of occurrences of a subsequence of length three in a string ; calculate length of string ; auxiliary array to store occurrences of first character ; auxiliary array to store occurrences of third character ; calculate occurrences of first character upto ith index from left ; calculate occurrences of third character upto ith index from right ; variable to store total number of occurrences ; loop to find the occurrences of middle element ; if middle character of subsequence is found in the string ; multiply the total occurrences of first character before middle character with the total occurrences of third character after middle character ; Driver code
def findOccurrences ( str1 , substr ) : NEW_LINE INDENT n = len ( str1 ) NEW_LINE preLeft = [ 0 for i in range ( n ) ] NEW_LINE preRight = [ 0 for i in range ( n ) ] NEW_LINE if ( str1 [ 0 ] == substr [ 0 ] ) : NEW_LINE INDENT preLeft [ 0 ] += 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if ( str1 [ i ] == substr [ 0 ] ) : NEW_LINE INDENT preLeft [ i ] = preLeft [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT preLeft [ i ] = preLeft [ i - 1 ] NEW_LINE DEDENT DEDENT if ( str1 [ n - 1 ] == substr [ 2 ] ) : NEW_LINE INDENT preRight [ n - 1 ] += 1 NEW_LINE DEDENT i = n - 2 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT if ( str1 [ i ] == substr [ 2 ] ) : NEW_LINE INDENT preRight [ i ] = preRight [ i + 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT preRight [ i ] = preRight [ i + 1 ] NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT counter = 0 NEW_LINE for i in range ( 1 , n - 1 ) : NEW_LINE INDENT if ( str1 [ i ] == str1 [ 1 ] ) : NEW_LINE INDENT total = preLeft [ i - 1 ] * preRight [ i + 1 ] NEW_LINE counter += total NEW_LINE DEDENT DEDENT return counter NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str1 = " GFGFGYSYIOIWIN " NEW_LINE substr = " GFG " NEW_LINE print ( findOccurrences ( str1 , substr ) ) NEW_LINE DEDENT