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, 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

    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