Given a string s of lowercase alphabets and a number k, the task is to print the minimum value of the string after removal of k characters. The value of a string is defined as the sum of squares of the count of each distinct character present in the string.
Example 1:
Input:
s = abccc, k = 1
Output:
6
Explaination:
We remove c to get the value as 12 + 12 + 22
Example 2:
Input:
s = aabcbcbcabcc, k = 3
Output:
27
Explaination:
We remove two 'c' and one 'b'. Now we get the value as 3^2 + 3^2 + 3^2.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minValue() which takes s and k as input parameters and returns the minimum possible required value.
Expected Time Complexity: O(n+klog(p)) where n is the length of string and p is number of distinct alphabets and k number of alphabets to be removed.
Expected Auxiliary Space: O(n)
Constraints:
0 ≤ k ≤ |string length| ≤ 10^5
Implementation
#User function Template for python3
class Solution:
def minValue(self, s, k):
# Count the frequency of each character in the string
frequency = {}
for char in s:
frequency[char] = frequency.get(char, 0) + 1
# Sort the frequencies in descending order
sorted_freq = sorted(frequency.values(), reverse=True)
# Greedily remove characters starting from the least frequent
for _ in range(k):
if not sorted_freq:
break
sorted_freq[0] -= 1
if sorted_freq[0] == 0:
sorted_freq.pop(0)
sorted_freq.sort(reverse=True)
# Calculate the value of the modified string
value = sum(freq ** 2 for freq in sorted_freq)
return value
#{
# Driver Code Starts
#Initial Template for Python 3
if __name__ == '__main__':
t = int(input())
for _ in range(t):
s = input()
k = int(input())
ob = Solution()
print(ob.minValue(s, k))
# } Driver Code Ends