# Solving Leetcode Interviews in Seconds with AI: Sum of Beauty of All Substrings


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1781" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.  For example, the beauty of "abaacc" is 3 - 1 = 2.  Given a string s, return the sum of beauty of all of its substrings.   Example 1:  Input: s = "aabcb" Output: 5 Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1. Example 2:  Input: s = "aabcbaa" Output: 17    Constraints:  1 <= s.length <= 500 s consists of only lowercase English letters.  

	# Explanation
	Here's a breakdown of the approach, complexity, and the Python code:

*   **Approach:** Iterate through all possible substrings of the given string. For each substring, calculate the frequency of each character, find the maximum and minimum frequency, and compute the beauty. Sum up the beauty of all substrings.

*   **Complexity:**
    *   Runtime: O(n^3), where n is the length of the string. This is due to the nested loops for generating substrings (O(n^2)) and the frequency calculation within each substring (O(n)).
    *   Storage: O(1). The character frequency map uses constant space (at most 26 lowercase letters), and other variables use constant space.

*   **Python Code:**

	
	# Code
	```python
	def beautySum(s: str) -> int:
    """
    Calculates the sum of beauty of all substrings of a given string.

    Args:
        s: The input string.

    Returns:
        The sum of beauty of all substrings.
    """

    total_beauty = 0
    n = len(s)

    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            char_counts = {}
            for char in substring:
                char_counts[char] = char_counts.get(char, 0) + 1

            if not char_counts:
                continue

            max_freq = 0
            min_freq = float('inf')

            for char in char_counts:
                freq = char_counts[char]
                max_freq = max(max_freq, freq)
                min_freq = min(min_freq, freq)

            total_beauty += max_freq - min_freq

    return total_beauty
	```