Beautiful Collection - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To calculate the sum of beauty of all substrings in the given string collection.
  • What input is provided?
    • A string collection.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: For each substring, calculate the difference between the maximum and minimum frequency of characters, then sum up these values.

1) Initialize `total_beauty` to 0.
2) Iterate through all possible substrings of `collection`.
3) For each substring, calculate the frequency of characters and determine the beauty.
4) Add the beauty of each substring to `total_beauty`.
5) Return `total_beauty`.

⚠️ Common Mistakes

• Incorrectly calculating the beauty by not properly identifying the maximum and minimum frequencies.

I-mplement

def beauty_sum(collection):
    total_beauty = 0
    
    # Generate all substrings
    for i in range(len(collection)):
        freq = {}
        for j in range(i, len(collection)):
            char = collection[j]
            if char in freq:
                freq[char] += 1
            else:
                freq[char] = 1
            
            # Calculate the beauty of the current substring
            max_freq = max(freq.values())
            min_freq = min(freq.values())
            
            total_beauty += (max_freq - min_freq)
    
    return total_beauty