Minimum Length Of String After Deleting Similar Ends - Leetcode Solution

Problem Statement:

Given a string s consisting only of 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 the resulting string.

Return the minimum number of characters you have to delete to make s satisfy the above condition.

Example 1:

Input: s = "eeeeffff" Output: 1 Explanation: We can delete one occurrence of 'e' or one occurrence of 'f'. Then one letter will occur four times and the other three times.

Example 2:

Input: s = "aabbffddeaee" Output: 6 Explanation: For example, we can delete all occurrences of 'e' and 'f' and one occurrence of 'd' to obtain the word "aabbda". Note that both 'a' and 'b' occur twice.

Example 3:

Input: s = "llllcccc" Output: 0 Explanation: Both 'l' and 'c' occur 4 times in s. Hence, we do not need to delete anything.

Approach:

A simple solution to this problem would be to keep deleting characters from the ends until the string satisfies the given condition. This is because deleting characters from the middle of the string will not decrease the length of the final string. Once we have a string where all the letters appear a unique number of times, we can return the number of characters we deleted.

Algorithm:

1. Initialize two counters, one for the beginning of the string (left) and one for the end of the string (right).
2. Keep incrementing left and decrementing right until the counts of each letter in the substring s[left..right] all appear a unique number of times.
3. At this point, the minimum length of the string after deleting the similar ends would be len(s) - (right - left + 1).
4. Return this minimum length.

Code:

class Solution: def minimumLength(self, s: str) -> int: left, right = 0, len(s) - 1 counts = collections.Counter(s) while left < right and counts[s[left]] > 1: counts[s[left]] -= 1 left += 1 while right >= left and counts[s[right]] > 1: counts[s[right]] -= 1 right -= 1 return len(s) - (right - left + 1)

Complexity Analysis:

Time Complexity: O(n).

We traverse the string twice, once from the beginning and once from the end. But since we are only traversing a substring, the time complexity becomes linear, i.e., O(n). Here, n is the length of the input string.

Space Complexity: O(1).

We are only using a constant amount of extra space. Therefore, the space complexity is O(1).

1