Calculate Sum of ratio of special characters to length of substrings of the given string | C ++ 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 ;
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1e5 + 5 ; vector < int > prefix ( N , 0 ) ; vector < int > sum ( N , 0 ) ; bool isSpecial ( char c , vector < char > & special ) { for ( auto & i : special ) if ( i == c ) return true ; return false ; } double countRatio ( string & s , vector < char > & special ) { int n = s . length ( ) ; for ( int i = 0 ; i < n ; i ++ ) { prefix [ i ] = int ( 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 ; } int main ( ) { string s = " abcd " ; vector < char > special = { ' b ' , ' c ' } ; double ans = countRatio ( s , special ) ; cout << fixed << setprecision ( 6 ) << ans << endl ; return 0 ; }