BinarySearch 0827 Unique String Frequencies

Problem statement

https://binarysearch.com/problems/Unique-String-Frequencies/

Solution

Similar to Leetcode 0945. Minimum Increment to Make Array Unique, but here we need to decrease.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, s):
        nums = sorted(list(Counter(s).values()))[::-1]
        nums2 = nums[:]
        n = len(nums)

        for i in range(1, n):
            nums2[i] = max(min(nums2[i-1] - 1, nums[i]), 0)
        return sum(y - x for x, y in zip(nums2, nums))