Last Updated: 11 May, 2023
Sum Of Beauty Of All Substrings
Easy
Asked in company
You are given a string ‘S’ of length ‘N’ representing an integer.
Beauty of a string is the difference between the frequency of the most frequently occurring character and the least frequently occurring character.
You must return the sum of beauty of all substrings of string ‘S’.
Note:
A substring is a string formed after deleting zero or more characters from both ends of a string.
Example:
Input:
S = “hello"
Output:
5
Explanation: The following substring ‘hell’, ‘ell’, ‘llo’, ‘ello’, and ‘hello’ has the beauty of 1. Hence we return 5.
Input Format:
The first line of the input will contain an integer ‘N’ denoting the length of the string ‘S’.
The next line contains the string ’S’.
Output Format:-
Output is printed on a separate line.
Note:-
You don’t need to print anything. Just implement the given function.
Approaches
Approach:
- We can generate all the substrings and calculate the frequency of each character for every substring.
- The beauty of each substring is calculated by the difference between the highest and the lowest frequency.
Algorithm:
Function int sumOfBeauty(string S):
- Generate all substrings and store them in an array of strings, ‘subStrings’.
- Initialize an integer variable ‘answer’ with 0.
- For each string ‘subString’ in subStrings:
- Initialize an integer array ‘freq’ of length 26 with 0;
- For each character ‘i’ in ‘subString’:
- Increment ‘freq[‘i’-’a’]’ by one.
- Initialise integer variables ‘maxFrequency’ and ‘minFrequency’ with 0 and INT_MAX, respectively.
- For ‘i’ from 0 to 25:
- ‘maxFrequency’=max(‘maxFrequency’, freq[i])
- ‘minFrequency’=min(‘minFrequency’, freq[i])
- ‘answer’+=’maxFrequency’-’minFrequency’
- Return ‘answer’
Approach:
- We initialize our ‘answer’ variable with zero.
- We generate a window of length 2 to ‘N’ and calculate the frequency of each character in the window.
- Now we shift our window to the right. We can calculate the new window's frequency by deleting the previous window's first character and adding the current window's last character.
- Calculate each window's minimum and maximum frequency and add it to the answer.
- Return the answer at the end.
Algorithm:
Function int sumOfBeauty(string S):
- Initialize an integer variable ‘answer’ with zero.
- Int ‘N’ = ‘S.length()’
- For ‘len’ from 2 to ‘N’:
- Initialize an integer array ‘freq’ of length 26 with 0;
- For ‘i’ from 0 to ‘len’-1:
- Increment ‘freq[‘S[i]’ - ‘a’]’ by one.
- ‘answer’+= maximum(‘cnt’) - minimum(‘freq’)
- For ‘i’ from ‘len’ to ‘N’-1:
- Decrement ‘freq[ S[ ‘i’-’len’ ] - ‘a’]’ by one.
- Increment ‘freq[‘S[i]’ - ‘a’]’ by one.
- ‘answer’+= maximum(‘freq’) - minimum(‘freq’)
- Return ‘answer’.