Minimum Number Of Operations To Make String Sorted - Leetcode Solution

Problem Statement:

Given a string s consisting of n lowercase letters, you have to delete the minimum number of characters from s so that every letter in s appears a unique number of times. We only care about the occurrences of letters that appear at least once in result. Return the minimum number of deletions needed.

Example:

Input: s = "aab" Output: 0 Explanation: s is already good.

Input: s = "aaabbbcc" Output: 2 Explanation: You can delete two 'b's resulting in the good string "aabcc".

Approach:

• We need to find the minimum number of deletions required to make the string sorted.
• The first step would be to count the frequency of each character in the string. This can be done using a dictionary or an array of size 26 (assuming we only have lowercase letters).
• Once we have the frequency of each character in the string, we need to sort the frequency values in ascending order. We can use a heap for this purpose.
• Now, we start iterating through the sorted frequency values. For each value, we check if it is equal to or less than the current count of unique frequencies. If yes, we do not need to delete any characters. If no, we need to delete the excess characters.
• We keep a count of the number of deletions required and return it.

Code:

The code for the implementation of the above approach is given below.

Time Complexity: O(NlogN), where N is the length of the input string. Space Complexity: O(26) = O(1)

class Solution: def minDeletions(self, s: str) -> int: freq_dict = {} for char in s: if char not in freq_dict: freq_dict[char] = 0 freq_dict[char] += 1

    heap = []
    for freq in freq_dict.values():
        heapq.heappush(heap, -freq)
        
    count = 0
    unique_freq = set()
    while heap:
        freq = -heapq.heappop(heap)
        if freq in unique_freq:
            freq -= 1
            count += 1
        while freq > 0 and freq in unique_freq:
            freq -= 1
            count += 1
        unique_freq.add(freq)
        
    return count

1