Calculate Sum of ratio of special characters to length of substrings of the given string | Java 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 ;
import java . util . * ; class GFG { static int N = 1000000 + 5 ; static int [ ] prefix = new int [ N ] ; static int [ ] sum = new int [ N ] ; static int isSpecial ( char c , char [ ] special ) { for ( char i : special ) if ( i == c ) return 1 ; return 0 ; } static double countRatio ( char [ ] s , char [ ] special ) { int n = s . length ; for ( int i = 0 ; i < n ; i ++ ) { prefix [ i ] = ( isSpecial ( s [ i ] , special ) ) ; if ( i > 0 ) prefix [ i ] += prefix [ i - 1 ] ; } for ( int i = 0 ; i < n ; i ++ ) { sum [ i ] = prefix [ i ] ; if ( i > 0 ) sum [ i ] += sum [ i - 1 ] ; } double ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { int count = sum [ n - 1 ] - ( i > 1 ? sum [ i - 2 ] : 0 ) ; count -= ( i < n ? sum [ n - i - 1 ] : 0 ) ; ans += ( double ) count / ( double ) i ; } return ans ; } public static void main ( String [ ] args ) { String s = " abcd " ; char [ ] special = { ' b ' , ' c ' } ; double ans = countRatio ( s . toCharArray ( ) , special ) ; System . out . format ( " % .6f " , ans ) ; } }