Calculate Sum of ratio of special characters to length of substrings of the given string | Python3 program to implement the above approach ; Stores frequency of special characters in the array ; Stores prefix sum ; Function to check whether a character is special or not ; If current character is special ; Otherwise ; Function to find sum of ratio of count of special characters and length of substrings ; Calculate the prefix sum of special nodes ; Generate prefix sum array ; Calculate ratio for substring ; Driver Code
N = 100005 NEW_LINE prefix = [ 0 ] * N NEW_LINE sum = [ 0 ] * N NEW_LINE def isSpecial ( c , special ) : NEW_LINE INDENT for i in special : NEW_LINE INDENT if ( i == c ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def countRatio ( s , special ) : NEW_LINE INDENT n = len ( s ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT prefix [ i ] = int ( isSpecial ( s [ i ] , special ) ) NEW_LINE if ( i > 0 ) : NEW_LINE INDENT prefix [ i ] += prefix [ i - 1 ] NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT sum [ i ] = prefix [ i ] NEW_LINE if ( i > 0 ) : NEW_LINE INDENT sum [ i ] += sum [ i - 1 ] NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if i > 1 : NEW_LINE INDENT count = sum [ n - 1 ] - sum [ i - 2 ] NEW_LINE DEDENT else : NEW_LINE INDENT count = sum [ n - 1 ] NEW_LINE DEDENT if i < n : NEW_LINE INDENT count -= sum [ n - i - 1 ] NEW_LINE DEDENT ans += count / i NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abcd " NEW_LINE special = [ ' b ' , ' c ' ] NEW_LINE ans = countRatio ( s , special ) NEW_LINE print ( ' % .6f ' % ans ) NEW_LINE DEDENT