Sum Of Beauty Of All Substrings

Easy
0/40
profile
Contributed by
31 upvotes
Asked in company
Provakil

Problem statement

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.


Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
4
aaaa


Sample Output 1:
0


Explanation Of Sample Input 1:
For test case one:

Input:
S = 'aaaa', N = 4

Output:
0

Explanation: All substrings have the same character. Hence all the substrings have a beauty of 0. 
Hence we return 0.


Sample Input 2:
8
tortoise


Sample Output 2:
9


Constraints:
1 <= N <= 500
’S’ consists of lowercase English letters.    
Time Limit: 1 sec
Follow Up:
Can you solve this in O(N) time?
Hint

Simulate the problem statement.

Approaches (2)
Brute Force

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):

  1. Generate all substrings and store them in an array of strings, ‘subStrings’.
  2. Initialize an integer variable ‘answer’ with 0.
  3. 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’
  4. Return ‘answer’
Time Complexity

Time Complexity: O( N^2* max(N, K) ), Where 'N' is the string 'S' length and 'K' is the number of lowercase English letters.
 

We are generating all substrings, which takes a time complexity of O(N^2), and for each substring, we check the frequency of each character. Hence, the overall time complexity will be O(N^2 * K). 

Space Complexity

O( N^3 ), Where ‘N’ is the string ‘S’ length. 
 

We are taking O( N^3 ) extra space for storing the substrings. Hence, the overall space complexity will be O( N^3 ).

Code Solution
(100% EXP penalty)
Sum Of Beauty Of All Substrings
Full screen
Console