[LeetCode] 1636. Sort Array by Increasing Frequency

 Problem : https://leetcode.com/problems/sort-array-by-increasing-frequency/

This is a bucket sort problem. Firstly put numbers with same frequency into same bucket. Then reverse sort numbers in the same bucket.

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        bucket = defaultdict(list)
        
        for n, c in Counter(nums).items():
            bucket[c].append(n) 
            
        result = []
        
        for c in range(101):
            for n in sorted(bucket[c], reverse=True): 
                result += [n] * c
        
        return result

[LeetCode] 828. Count Unique Characters of All Substrings of a Given String

 Problem : https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/

Instead of counting substrings, count the contribution of each unique character.

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        N = len(s)
        
        seen = defaultdict(lambda: -1)
        left = [0] * N   # the left side window in which the ith character is unique
        
        for i in range(N):
            left[i] = seen[s[i]]
            seen[s[i]] = i
        
        seen = defaultdict(lambda: N)
        right = [0] * N  # the right side window in which the ith character is unique
        
        for i in reversed(range(N)):
            right[i] = seen[s[i]]
            seen[s[i]] = i
        
        
        result = 0
        
        for i in range(N):
            # ith character can be unique in (left window size) * (right window size) substrings. 
            result += (i - left[i]) * (right[i] -i)
        
        return result
        

[LeetCode] 1167. Minimum Cost to Connect Sticks

 Problem : https://leetcode.com/problems/minimum-cost-to-connect-sticks/

Greedily connect the 2 shortest sticks in each round. Use heap to find the 2 shortest sticks.

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        result = 0
        
        heapq.heapify(sticks)
        
        while len(sticks) > 1:
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            c = a + b
            result += c
            heapq.heappush(sticks, c)
        
        return result

[LeetCode] 1710. Maximum Units on a Truck

 Problem : https://leetcode.com/problems/maximum-units-on-a-truck/

Greedily take the largest boxes first. Use heap to avoid sort all boxes.

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        heap = [(-m, -n) for n, m in boxTypes]
        heapq.heapify(heap)
        
        result = 0
        
        while truckSize and heap:
            m, n = heapq.heappop(heap)
            m, n = -m, -n
            
            taken = min(truckSize, n)
            result += m * taken
            
            truckSize -= taken
            
        return result