Calculate Sum of ratio of special characters to length of substrings of the given string
Given a string str and an array of special characters, specialArray[], the task is to find the sum of the ratio of the count of special characters to the length of the substring for all possible substring of the given string.
Ratio of count of special characters in a substring to the length of substrings of the given string is given by
Sum of the ratios calculated above is given by
Examples:
Input: str = “abcdabc”, specialArray[] = {‘a’, ‘b’, ‘c’, ‘d’}
Output: 28.00000
Explanation:
Length of string = 7
Count of all possible substrings = (7 * (8 + 1)) / 2 = 28
Since, all the characters of the string are included in specialArray[], ratio of count of special characters to the length of substring for every substring will always be 1.
Hence, the sum of ratio = Number of substrings * 1 = 28.Input: str = “abcd”, specialArray[] = {‘b’, ‘c’}
Output: 5.83333
Approach:
Follow the steps below to solve the problem:
- For every possible length of substrings from 1 to N, find the count of special characters in every substring of length x and add the ratio of count and x to the answer.
- To find the count of special characters in each substring in constant time, create a prefix sum array of the count of special characters using the relation:
prefix[i] = prefix[i – 1] + special(s[i]);
- Calculate the count of special characters in a substring within the indices [i, j] is given by the relation:
prefix[j – 1] – prefix[i – 1]
Therefore, the ratio of the count of special characters to the length of substring,
f(i, j) = (prefix[j – 1] – prefix[i – 1])/(j – i + 1)
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; // Stores frequency of special // characters in the array vector< int > prefix(N, 0); // Stores prefix sum vector< int > sum(N, 0); // Function to check whether a character // is special or not bool isSpecial( char c, vector< char >& special) { for ( auto & i : special) // If current character // is special if (i == c) return true ; // Otherwise return false ; } // Function to find sum of ratio of // count of special characters and // length of substrings double countRatio(string& s, vector< char >& special) { int n = s.length(); for ( int i = 0; i < n; i++) { // Calculate the prefix sum of // special nodes prefix[i] = int (isSpecial(s[i], special)); if (i > 0) prefix[i] += prefix[i - 1]; } for ( int i = 0; i < n; i++) { // Generate prefix sum array sum[i] = prefix[i]; if (i > 0) sum[i] += sum[i - 1]; } double ans = 0; for ( int i = 1; i <= n; i++) { // Calculate ratio for substring 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; } // Driver Code; int main() { string s = "abcd" ; vector< char > special = { 'b' , 'c' }; double ans = countRatio(s, special); cout << fixed << setprecision(6) << ans << endl; return 0; } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG{ static int N = 1000000 + 5 ; // Stores frequency of special // characters in the array static int []prefix = new int [N]; // Stores prefix sum static int []sum = new int [N]; // Function to check // whether a character // is special or not static int isSpecial( char c, char [] special) { for ( char i : special) // If current character // is special if (i == c) return 1 ; // Otherwise return 0 ; } // Function to find sum of ratio of // count of special characters and // length of subStrings static double countRatio( char []s, char [] special) { int n = s.length; for ( int i = 0 ; i < n; i++) { // Calculate the prefix sum of // special nodes prefix[i] = (isSpecial(s[i], special)); if (i > 0 ) prefix[i] += prefix[i - 1 ]; } for ( int i = 0 ; i < n; i++) { // Generate prefix sum array sum[i] = prefix[i]; if (i > 0 ) sum[i] += sum[i - 1 ]; } double ans = 0 ; for ( int i = 1 ; i <= n; i++) { // Calculate ratio for subString 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; } // Driver Code; public static void main(String[] args) { String s = "abcd" ; char [] special = { 'b' , 'c' }; double ans = countRatio(s.toCharArray(), special); System.out.format( "%.6f" ,ans); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program to implement # the above approach N = 100005 # Stores frequency of special # characters in the array prefix = [ 0 ] * N # Stores prefix sum sum = [ 0 ] * N # Function to check whether a character # is special or not def isSpecial(c, special): for i in special: # If current character # is special if (i = = c): return True # Otherwise return False # Function to find sum of ratio of # count of special characters and # length of substrings def countRatio(s, special): n = len (s) for i in range (n): # Calculate the prefix sum of # special nodes prefix[i] = int (isSpecial(s[i], special)) if (i > 0 ): prefix[i] + = prefix[i - 1 ] for i in range (n): # Generate prefix sum array sum [i] = prefix[i] if (i > 0 ): sum [i] + = sum [i - 1 ] ans = 0 for i in range ( 1 , n + 1 ): # Calculate ratio for substring if i > 1 : count = sum [n - 1 ] - sum [i - 2 ] else : count = sum [n - 1 ] if i < n: count - = sum [n - i - 1 ] ans + = count / i return ans # Driver Code if __name__ = = "__main__" : s = "abcd" special = [ 'b' , 'c' ] ans = countRatio(s, special) print ( '%.6f' % ans) # This code is contributed by chitranayal |
C#
// C# Program to implement // the above approach using System; class GFG{ static int N = 1000000 + 5; // Stores frequency of special // characters in the array static int []prefix = new int [N]; // Stores prefix sum static int []sum = new int [N]; // Function to check // whether a character // is special or not static int isSpecial( char c, char [] special) { foreach ( char i in special) // If current character // is special if (i == c) return 1; // Otherwise return 0; } // Function to find sum of ratio of // count of special characters and // length of subStrings static double countRatio( char []s, char [] special) { int n = s.Length; for ( int i = 0; i < n; i++) { // Calculate the prefix sum of // special nodes prefix[i] = (isSpecial(s[i], special)); if (i > 0) prefix[i] += prefix[i - 1]; } for ( int i = 0; i < n; i++) { // Generate prefix sum array sum[i] = prefix[i]; if (i > 0) sum[i] += sum[i - 1]; } double ans = 0; for ( int i = 1; i <= n; i++) { // Calculate ratio for subString 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; } // Driver Code; public static void Main(String[] args) { String s = "abcd" ; char [] special = { 'b' , 'c' }; double ans = countRatio(s.ToCharArray(), special); Console.WriteLine( "{0:F6}" , ans); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to implement // the above approach var N = 1000005; // Stores frequency of special // characters in the array var prefix = Array(N).fill(0); // Stores prefix sum var sum = Array(N).fill(0); // Function to check whether a character // is special or not function isSpecial(c, special) { var ans = false ; special.forEach(i => { // If current character // is special if (i == c) ans = true ; }); // Otherwise return ans; } // Function to find sum of ratio of // count of special characters and // length of substrings function countRatio(s, special) { var n = s.length; for ( var i = 0; i < n; i++) { // Calculate the prefix sum of // special nodes prefix[i] = (isSpecial(s[i], special)); if (i > 0) prefix[i] += prefix[i - 1]; } for ( var i = 0; i < n; i++) { // Generate prefix sum array sum[i] = prefix[i]; if (i > 0) sum[i] += sum[i - 1]; } var ans = 0; for ( var i = 1; i <= n; i++) { // Calculate ratio for substring var count = sum[n - 1] - ((i > 1) ? sum[i - 2] : 0); count -= ((i < n) ? sum[n - i - 1] : 0); ans += ((count) / (i)); } return ans; } // Driver Code; var s = "abcd" ; var special = [ 'b' , 'c' ]; var ans = countRatio(s.split( '' ), special); document.write( ans.toFixed(6)); // This code is contributed by itsok </script> |
Output:
5.833333
Time Complexity: O(N)
Space Complexity: O(N)