1781. Sum of Beauty of All Substrings
Problem Description
The problem asks us to calculate the "beauty" of a string. The beauty of a string is defined as the difference between the number of occurrences of the most frequent character and the least frequent character in that string. We are to find the beauty of every possible substring of the given string and then sum up these beauties to get a final answer.
Substrings of a string are the sequences of characters that can be derived from the string by deleting some characters (possibly, none) from the beginning or end of the string. For instance, "ab", "b", "baa", etc. are all substrings of the string "abaacc".
To further clarify the problem, let's take the example given in the problem description: For the string "abaacc", the beauty of this string is calculated by looking at the frequency of each character. The character 'a' appears 3 times, 'b' once, and 'c' twice. The most frequent character is 'a', with a frequency of 3, and the least frequent (excluding characters not present at all) is 'b', with a frequency of 1. So, the beauty of the string "abaacc" is 3 - 1 = 2.
What the problem ultimately requires us to do is calculate such beauties for all substrings of the input string 's' and return their sum.
Intuition
The solution adopts a brute-force approach to finding all possible substrings and calculating the beauty of each. Breaking down our approach intuitively:
-
We will iterate over every possible starting point for a substring within the string 's'. This is done by a loop indexed by 'i' going from the start to the end of 's'.
-
For each starting point 'i', we will then iterate over all possible ending points. These are determined by the loop indexed by 'j', which goes from 'i' to the end of 's'.
-
As we expand our substring from 'i' to 'j', we will keep track of the frequencies of the characters appearing in the substring using a
Counter(which is essentially a specialized dictionary or hash map provided by Python's collections library). -
At each iteration, as we increase the size of the current substring by extending 'j', we calculate the beauty of the new substring by finding the frequency of the most and least frequent characters in our
Counter. This is the difference betweenmax(cnt.values())andmin(cnt.values()). -
We add this beauty to a running total 'ans', which, at the end of the process, will contain the sum of beauties of all substrings.
The brute-force solution may not be the most efficient, especially for very long strings, because the number of substrings grows rapidly. However, it is a straightforward method that guarantees a correct solution by exhaustively checking every option.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Solution Approach
The implementation of the provided solution follows a brute-force approach and iteratively calculates the beauty of all possible substrings of the input string. Let's delve into the specifics:
-
Two Nested Loops: The algorithm uses two nested loops, which enables it to consider every possible substring of the input string. The outer loop (indexed by
i) represents the start of the substring, while the inner loop (indexed byj) represents the end. -
Counter: A
Counterfrom Python's collections library is used to track character frequencies within the current substring. This data structure allows us to efficiently keep a tally as we extend our substring by adding characters one by one. -
Updating Counter: Within the inner loop, the counter is updated every time a new character is added to the substring:
cnt[s[j]] += 1. This line increments the count of the character at the current end positionj. -
Calculating Beauty: After each update to the counter, the beauty of the new substring is determined by finding the maximum and minimum values of
cnt. This is executed bymax(cnt.values()) - min(cnt.values()). It represents the frequency of the most common character minus the frequency of the least common character in the current substring. -
Summing Up the Beauties: The beauty found at each step is then added to a running total
ans, which eventually becomes the answer. This occurs in the expressionans += max(cnt.values()) - min(cnt.values()). -
Returning the Result: After all iterations, the outer loop concludes, and the final value of
ans—which, at this point, holds the accumulated beauty of all substrings—is returned as the result of the function.
This algorithm is straightforward but not particularly efficient, as it has a time complexity of O(n^3) considering that there are n*(n+1)/2 possible substrings and for each substring we are computing the beauty in O(n) time. This is an exhaustive method that guarantees the correct summation of the beauties for all substrings but might not scale well for large strings due to its polynomial time complexity.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
Example Walkthrough
Let's take a small string "abc" to illustrate the solution approach.
For this string "abc", the possible substrings along with their beauties (difference between most frequent and least frequent character counts) will be:
- "a" -> Beauty: 0 (since there is only one character)
- "b" -> Beauty: 0 (since there is only one character)
- "c" -> Beauty: 0 (since there is only one character)
- "ab" -> Beauty: 0 (both 'a' and 'b' occur exactly once)
- "bc" -> Beauty: 0 (both 'b' and 'c' occur exactly once)
- "abc" -> Beauty: 0 (all characters 'a', 'b', and 'c' occur exactly once)
Now, following the solution approach steps:
-
Two Nested Loops: We start with the outer loop where
igoes from 0 to 2 (the length of the string - 1) to take each character as the starting point. For each value ofi, we enter the inner loop, wherejalso ranges fromito 2. -
Counter: We initialize an empty Counter object
cntat the start of each iteration of the outer loop because we are starting a new substring. -
Updating Counter: For each pair
(i, j), we increment the count ofs[j]in ourCounterby 1, thereby updating the frequency of the current character. -
Calculating Beauty: We then calculate the beauty of this particular substring as
max(cnt.values()) - min(cnt.values()). Since all characters in our substrings occur at most once, this beauty is always 0 in the case of the example string "abc". -
Summing Up the Beauties: For each new substring, the calculated beauty (which is always 0 for our example "abc") is added to the running total
ans. -
Returning the Result: After all iterations of both loops, we conclude that the sum of the beauties is 0 since all our substrings have characters appearing only once.
Therefore, for the input string "abc", our function would return the sum of the beauties of all substrings, which is 0 in this case. Remember, this method does indeed scale poorly for larger strings, as it must compute the beauty of each substring individually, which becomes exponentially greater as the length of the string increases.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def beautySum(self, s: str) -> int:
5 # Initialize the sum to store the total beauty of all substrings
6 total_beauty = 0
7 # Get the length of the string
8 string_length = len(s)
9
10 # Iterate through each character in the string as the starting point
11 for i in range(string_length):
12 # Create a counter to keep track of the frequency of each character in the current substring
13 char_counter = Counter()
14 # Iterate from the current character to the end of the string to form substrings
15 for j in range(i, string_length):
16 # Increment the count of the current character
17 char_counter[s[j]] += 1
18 # Calculate the beauty of the current substring by finding the
19 # difference between the max and min frequency of characters
20 current_beauty = max(char_counter.values()) - min(char_counter.values())
21 # Add the beauty of the current substring to the total beauty
22 total_beauty += current_beauty
23 # Return the total beauty of all substrings
24 return total_beauty
251class Solution {
2 public int beautySum(String s) {
3 int totalBeauty = 0; // This will hold the cumulative beauty sum
4 int stringLength = s.length(); // Store the length of string s
5
6 // Outer loop to go through the substring starting points
7 for (int i = 0; i < stringLength; ++i) {
8 int[] frequencyCount = new int[26]; // Frequency array to count letters in the substring
9
10 // Inner loop to go through the substrings ending with character at position j
11 for (int j = i; j < stringLength; ++j) {
12 // Increment the frequency count of current character
13 ++frequencyCount[s.charAt(j) - 'a'];
14
15 // Set initial max and min frequency of characters. 1000 is assumed to be greater
16 // than any possible frequency thus a decent starting value for the minimum.
17 int minFrequency = 1000, maxFrequency = 0;
18
19 // Loop through the frequency count array to find the highest and lowest frequency
20 // that is greater than zero (character is present)
21 for (int freq : frequencyCount) {
22 if (freq > 0) {
23 minFrequency = Math.min(minFrequency, freq);
24 maxFrequency = Math.max(maxFrequency, freq);
25 }
26 }
27
28 // Beauty is calculated as the difference between max and min frequency of
29 // characters in the substring. Add this to totalBeauty.
30 totalBeauty += maxFrequency - minFrequency;
31 }
32 }
33
34 // Return the cumulative beauty of all substrings
35 return totalBeauty;
36 }
37}
381class Solution {
2public:
3 // This function calculates the beauty sum of a string.
4 int beautySum(string s) {
5 int sum = 0; // Initialize sum to store the beauty sum result.
6 int n = s.size(); // Get the size of the string.
7 int charCounts[26]; // Array to count occurrences of each character (a-z).
8
9 // Iterate over the string starting with substrings of length 1 to n.
10 for (int start = 0; start < n; ++start) {
11 memset(charCounts, 0, sizeof charCounts); // Reset character counts for each new starting point.
12 // Explore all substrings starting at 'start' and ending at 'end'.
13 for (int end = start; end < n; ++end) {
14 // Increment the count of the current character.
15 ++charCounts[s[end] - 'a'];
16
17 // Initialize max and min occurrences of characters found so far.
18 int minFreq = 1000, maxFreq = 0;
19 // Iterate over the counts to find the max and min frequencies.
20 for (int count : charCounts) {
21 if (count > 0) { // Only consider characters that appear in the substring.
22 minFreq = min(minFreq, count);
23 maxFreq = max(maxFreq, count);
24 }
25 }
26 // Add the beauty (difference between max and min frequency) of this substring to the sum.
27 sum += maxFreq - minFreq;
28 }
29 }
30 // Return the total beauty sum of all substrings.
31 return sum;
32 }
33};
341/**
2 * Calculates the sum of beauty of all of its substrings.
3 * @param {string} s - The string to process.
4 * @return {number} - The sum of beauty of all substrings.
5 */
6const beautySum = (s: string): number => {
7 let beautySumResult: number = 0;
8 // Iterate through the string
9 for (let i = 0; i < s.length; ++i) {
10 // Keep track of the frequency of each character
11 const frequencyCounter: Map<string, number> = new Map();
12 // Consider all substrings starting with the character at index 'i'
13 for (let j = i; j < s.length; ++j) {
14 // Increment the frequency of the current character
15 frequencyCounter.set(s[j], (frequencyCounter.get(s[j]) || 0) + 1);
16 // Extract frequency values from the map to determine beauty
17 const frequencies: number[] = Array.from(frequencyCounter.values());
18 // The beauty of the substring is defined by the difference
19 // between the max and min frequency chars
20 beautySumResult += Math.max(...frequencies) - Math.min(...frequencies);
21 }
22 }
23 // Return the total beauty sum of all substrings
24 return beautySumResult;
25};
26
27// The function can be used as follows:
28// const result: number = beautySum("yourStringHere");
29What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Time and Space Complexity
Time Complexity
The provided code has two nested loops: the outer loop (indexed by i) iterating over the starting points in the string s, and the inner loop (indexed by j) iterating over the endpoints extending from the current starting point. For each inner iteration, it updates the Counter and calculates the beauty of the current substring.
The outer loop runs n times (where n is the length of s).
For each iteration of i, the inner loop runs up to n-i times.
In the worst case, where i is 0, the inner loop runs n times, and in the best case, where i is n-1, it runs once.
The update and calculation within the inner loop take O(k) time in the worst case, where k is the number of distinct characters in s since the Counter needs to iterate over all the keys to find the max and min values.
Therefore, the total time complexity is O(n^2 * k) where n is the length of the string and k is the number of unique characters.
Space Complexity
The space complexity is dictated by the Counter which stores the frequency of each character in the current substring.
In the worst case, the substring could contain all unique characters of the string. Hence, the space complexity is O(k) where k is the number of unique characters in the string s.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.