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.
 
Example 1:
Input: s = abccc, k = 1
Output: 6
Explaination:
We remove c to get the value as 1^{2} + 1^{2} + 2^{2}
 
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:
1 ≤ k ≤ |string length| ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def minValue(self, s, k):

        # code here

Solutions:
class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		p = []
		for i in d:
			p.append(d[i])
		p.sort()
		l = len(p)
		for i in range(k):
			z = p[l - 1] - 1
			p[l - 1] = z
			p.sort()
		m = 0
		for i in range(len(p)):
			m += p[i] * p[i]
		return m


class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			if d.get(i):
				d[i] += 1
			else:
				d[i] = 1
		arr = []
		for i in d.values():
			arr.append(i)
		total = len(s)
		cal = total - k
		avg = cal / len(arr)
		avg = int(avg) + (1 if avg > int(avg) else 0)
		arr = sorted(arr, reverse=True)
		c = 0
		max = arr[0]
		while k > 0:
			arr[0] -= 1
			k -= 1
			arr = sorted(arr, reverse=True)
		sum = 0
		for i in arr:
			sum += i * i
		return sum


class Solution:

	def minValue(self, s, k):
		result = 0
		d = {}
		for i in s:
			d[i] = d.get(i, 0) + 1
		l = list(d.values())
		for i in range(k):
			m = max(l)
			key = list(d.keys())[l.index(m)]
			d[key] = d[key] - 1
			l = list(d.values())
		for i in d.values():
			result += i ** 2
		return result


import heapq

class Solution:

	def minValue(self, s, k):
		l = [0] * 26
		for i in s:
			l[ord(i) - 97] -= 1
		heapq.heapify(l)
		while k >= 1:
			p = heapq.heappop(l)
			p += 1
			heapq.heappush(l, p)
			k -= 1
		res = 0
		for i in l:
			res += abs(i) ** 2
		return res


import heapq

class Solution:

	def minValue(self, s, k):
		hmap = {}
		su = 0
		for i in range(0, len(s)):
			if s[i] not in hmap:
				hmap[s[i]] = 1
			else:
				hmap[s[i]] += 1
		maxheap = []
		for (key, v) in hmap.items():
			heapq.heappush(maxheap, -v)
		for i in range(0, k):
			ele = -heapq.heappop(maxheap)
			heapq.heappush(maxheap, -(ele - 1))
		while len(maxheap) > 0:
			top = -heapq.heappop(maxheap)
			su = su + top * top
		return su


import heapq as h

class Solution:

	def minValue(self, s, k):
		s = sorted(s)
		ptr1 = 0
		ptr2 = 1
		count = 1
		square = 0
		temp = 0
		maxheap = []
		answer = 0
		while ptr2 < len(s):
			if s[ptr2] == s[ptr1]:
				count = count + 1
			else:
				h.heappush(maxheap, -count)
				ptr1 = ptr2
				count = 1
			ptr2 = ptr2 + 1
		h.heappush(maxheap, -count)
		while k > 0:
			temp = -h.heappop(maxheap)
			temp = temp - 1
			h.heappush(maxheap, -temp)
			k = k - 1
		while maxheap:
			temp = -h.heappop(maxheap)
			square = temp * temp
			answer = answer + square
		return answer


class Solution:

	def minValue(self, s, k):
		from queue import PriorityQueue
		pq = PriorityQueue()
		a = [0] * 26
		for i in s:
			a[ord(i) - ord('a')] += 1
		for i in range(26):
			if a[i]:
				pq.put(-a[i])
		k = min(k, len(s))
		while k:
			k -= 1
			l = pq.get()
			if l + 1:
				pq.put(l + 1)
		res = 0
		while not pq.empty():
			res += pq.get() ** 2
		return res


class Solution:

	def minValue(self, s, k):
		dict1 = {}
		for i in range(len(s)):
			x = dict1.get(s[i], 0)
			dict1[s[i]] = x + 1
		d1 = sorted(dict1.values())
		c = 0
		while c != k and d1 != []:
			a = max(d1)
			d1.remove(a)
			a -= 1
			d1.append(a)
			c += 1
		s = 0
		for i in d1:
			s += i ** 2
		return s


from queue import PriorityQueue
MAX_CHAR = 26

class Solution:

	def minValue(self, str, k):
		l = len(str)
		if k >= l:
			return 0
		frequency = [0] * MAX_CHAR
		for i in range(0, l):
			frequency[ord(str[i]) - 97] += 1
		q = PriorityQueue()
		for i in range(0, MAX_CHAR):
			q.put(-frequency[i])
		while k > 0:
			temp = q.get()
			temp = temp + 1
			q.put(temp, temp)
			k = k - 1
		result = 0
		while not q.empty():
			temp = q.get()
			temp = temp * -1
			result += temp * temp
		return result


import heapq

class Solution:

	def minValue(self, s, k):
		ans = 0
		dicti = {}
		for i in s:
			if i not in dicti:
				dicti[i] = 1
			else:
				dicti[i] += 1
		lst = [-value for (key, value) in dicti.items()]
		heapq.heapify(lst)
		while k:
			a = heapq.heappop(lst)
			a = abs(a) - 1
			heapq.heappush(lst, -a)
			k -= 1
		while len(lst) != 0:
			ans += heapq.heappop(lst) ** 2
		return ans


class Solution:

	def minValue(self, s, k):
		d = {}
		sum = 0
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		max_key = next(iter(d))
		while k > 0:
			for key in d.keys():
				if d[key] > d[max_key]:
					max_key = key
			d[max_key] -= 1
			k -= 1
		val = list(d.values())
		for i in val:
			sum += i * i
		return sum


from queue import PriorityQueue

def game_string(input_string: str, k):
	alphabet_map = {}
	for i in range(len(input_string)):
		char = input_string[i]
		alphabet_map[char] = alphabet_map[char] + 1 if char in alphabet_map else 1
	data_queue = PriorityQueue()
	for key in alphabet_map.keys():
		count = alphabet_map[key]
		data_queue.put(-count)
	for i in range(k):
		element = abs(data_queue.get())
		element = element - 1
		if element > 0:
			data_queue.put(-1 * element)
	answer = 0
	while len(data_queue.queue) > 0:
		element = data_queue.get()
		answer = answer + element ** 2
	return answer

class Solution:

	def minValue(self, s, k):
		return game_string(s, k)


from queue import PriorityQueue

class Solution:

	def minValue(self, s, k):
		arr = [0 for _ in range(26)]
		for c in s:
			idx = ord(c) - 97
			arr[idx] += 1
		queue = PriorityQueue()
		for v in arr:
			queue.put(-1 * v)
		while k > 0:
			temp = queue.get()
			temp += 1
			queue.put(temp)
			k -= 1
		ans = 0
		while not queue.empty():
			tmp = -1 * queue.get()
			tmp = tmp * tmp
			ans += tmp
		return ans


from collections import Counter

class Solution:

	def minValue(self, s, k):
		dict1 = Counter(s)
		for i in range(k):
			max_dict = max(dict1, key=dict1.get)
			dict1[max_dict] -= 1
		output = []
		for (i, j) in dict1.items():
			output.append(j)
		ans = 0
		for i in output:
			ans += i * i
		return ans


class Solution:

	def minValue(self, s, k):
		dic = {}
		for i in s:
			if i in dic.keys():
				dic[i] += 1
			else:
				dic[i] = 1
		l = list(dic.values())
		for i in range(k):
			val = l.index(max(l))
			l[val] = l[val] - 1
		l = [i ** 2 for i in l]
		return sum(l)


from collections import Counter

class Solution:

	def minValue(self, s, k):
		mp = Counter(s)
		l = list(mp.values())
		for i in range(k):
			val = l.index(max(l))
			l[val] = l[val] - 1
		l = [i ** 2 for i in l]
		return sum(l)


from collections import Counter

class Solution:

	def minValue(self, s, k):
		d = Counter(s)
		l = [j for (i, j) in d.items()]
		l.sort(reverse=True)
		for i in range(k):
			l[0] -= 1
			l.sort(reverse=True)
		return sum([i * i for i in l])


import heapq
from collections import Counter

class Solution:

	def minValue(self, s, k):
		ans = [j for (i, j) in Counter(s).items() if i != ' ']
		ans = list(map(lambda x: -x, ans))
		heapq.heapify(ans)
		while k:
			out = heapq.heappop(ans)
			out = out * -1
			out -= 1
			heapq.heappush(ans, -out)
			k -= 1
		return sum((i * i for i in ans))


class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 0
			d[i] += 1
		l = list(d.values())
		while k:
			i = l.index(max(l))
			l[i] -= 1
			k -= 1
		return sum([i ** 2 for i in l])


import heapq

class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		d1 = sorted(d.values())
		heapq.heapify(d1)
		c = 0
		while c != k and d1 != []:
			a = max(d1)
			d1.remove(a)
			a -= 1
			d1.append(a)
			c += 1
		s = 0
		for i in d1:
			s += i ** 2
		return s


class Solution:

	def minValue(self, s, k):
		dct = {}
		for ch in s:
			if ch not in dct:
				dct[ch] = 1
			else:
				dct[ch] += 1
		lst = list(dct.values())
		for j in range(k):
			maxi = max(lst)
			for i in range(len(lst)):
				if lst[i] == maxi:
					lst[i] -= 1
					break
		total = 0
		for i in lst:
			total += i ** 2
		return total


class Solution:

	def minValue(self, arr, k):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		valus = list(d.values())
		for i in range(k):
			v = valus.index(max(valus))
			valus[v] = valus[v] - 1
		return sum([i ** 2 for i in valus])


class Solution:

	def minValue(self, s, k):
		mp = dict()
		for i in range(len(s)):
			if s[i] in mp.keys():
				mp[s[i]] += 1
			else:
				mp[s[i]] = 1
		l = list(mp.values())
		for i in range(k):
			val = l.index(max(l))
			l[val] = l[val] - 1
		l1 = [i ** 2 for i in l]
		return sum(l1)


class Solution:

	def heappush(self, heap, data):
		heap.append(data)
		current = len(heap) - 1
		while current > 0:
			parent = (current - 1) // 2
			if heap[parent] < heap[current]:
				(heap[parent], heap[current]) = (heap[current], heap[parent])
				current = parent
			else:
				break

	def heappop(self, heap):
		if not heap:
			return 'Empty Heap!'
		elif len(heap) == 1:
			return heap.pop()
		(pop_data, heap[0]) = (heap[0], heap.pop())
		(current, child) = (0, 1)
		while child < len(heap):
			sibling = child + 1
			if sibling < len(heap) and heap[child] < heap[sibling]:
				child = sibling
			if heap[current] < heap[child]:
				(heap[current], heap[child]) = (heap[child], heap[current])
				current = child
				child = current * 2 + 1
			else:
				break
		return pop_data

	def minValue(self, s, k):
		h = {}
		for c in s:
			if c not in h:
				h[c] = 1
			else:
				h[c] += 1
		heap = []
		for v in h.values():
			self.heappush(heap, v)
		for _ in range(k):
			temp = self.heappop(heap) - 1
			self.heappush(heap, temp)
		answer = 0
		for value in heap:
			answer += value ** 2
		return answer


class Solution:

	def minValue(self, s, k):
		import heapq
		h = {}
		for c in s:
			if c not in h:
				h[c] = 1
			else:
				h[c] += 1
		heap = []
		for v in h.values():
			heapq.heappush(heap, -v)
		for _ in range(k):
			temp = heapq.heappop(heap) + 1
			heapq.heappush(heap, temp)
		answer = 0
		for value in heap:
			answer += (-value) ** 2
		return answer


class Solution:

	def minValue(self, s, k):
		d = {}
		for ch in s:
			if ch in d:
				d[ch] += 1
			else:
				d[ch] = 1
		mini = float('inf')
		maxfq = 0
		i = 0
		while i < k:
			maxchar = max(d, key=d.get)
			d[maxchar] -= 1
			i += 1
		ans = 0
		for key in d:
			ans += d[key] ** 2
		return ans


class Solution:

	def minValue(self, s, k):
		d = {}
		li = []
		for ele in s:
			d[ele] = d.get(ele, 0) + 1
		for ele in d:
			li.append(d[ele])
		li.sort()
		while k > 0:
			li[-1] -= 1
			li.sort()
			k -= 1
		x = 0
		for ele in li:
			x = x + ele * ele
		return x


import heapq

class Solution:

	def minValue(self, s, k):
		memo = {}
		for i in range(len(s)):
			memo[s[i]] = memo.get(s[i], 0) + 1
		heap = []
		for (key, value) in memo.items():
			heap.append((-value, key))
		heapq.heapify(heap)
		for i in range(k):
			(count, char) = heapq.heappop(heap)
			if count < -1:
				heapq.heappush(heap, (count + 1, char))
		ans = 0
		for items in heap:
			ans += items[0] ** 2
		return ans


import heapq

class Solution:

	def minValue(self, string, K):
		map = {}
		for item in string:
			map[item] = 1 + map.get(item, 0)
		heap = []
		for item in map.values():
			heapq.heappush(heap, -item)
		while K:
			temp = -1 * heapq.heappop(heap)
			temp -= 1
			heapq.heappush(heap, -temp)
			K -= 1
		result = 0
		while heap:
			item = -1 * heapq.heappop(heap)
			result += item ** 2
		return result


class Solution:

	def minValue(self, s, k):
		d = {}
		for i in range(len(s)):
			if s[i] in d:
				d[s[i]] += 1
			else:
				d[s[i]] = 1
		value = list(d.values())
		for i in range(k):
			val = value.index(max(value))
			value[val] -= 1
		return sum([i ** 2 for i in value])


from queue import PriorityQueue

class Solution:

	def minValue(self, s, k):
		dp = [0 for i in range(26)]
		for i in range(len(s)):
			dp[ord(s[i]) % ord('a')] += 1
		q = PriorityQueue()
		for i in range(26):
			if dp[i] != 0:
				q.put(0 - dp[i])
		while k > 0:
			z = q.get()
			z = z + 1
			q.put(z)
			k = k - 1
		ans = 0
		while not q.empty():
			z = q.get()
			z = 0 - z
			ans = ans + z * z
		return ans


import collections
from collections import Counter

class Solution:

	def minValue(self, s, k):
		d = dict(Counter(s))
		l = list(d.values())
		while k:
			ind = l.index(max(l))
			l[ind] = l[ind] - 1
			k -= 1
		return sum([i ** 2 for i in l])


class Solution:

	def minValue(self, s, k):
		dt = {}
		for i in range(len(s)):
			dt[s[i]] = 1 + dt.get(s[i], 0)
		while k != 0:
			m = max(zip(dt.values(), dt.keys()))[1]
			dt[m] -= 1
			k -= 1
		ans = 0
		for i in dt.values():
			ans += i * i
		return ans


import heapq

class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			d[i] = 1 + d.get(i, 0)
		heap = []
		for key in d:
			heap.append([d[key], key])
			heapq._siftdown_max(heap, 0, len(heap) - 1)
		while k:
			p = heapq._heappop_max(heap)
			heap.append([p[0] - 1, p[1]])
			heapq._siftdown_max(heap, 0, len(heap) - 1)
			k -= 1
		sum_ = 0
		while heap:
			p = heapq._heappop_max(heap)
			sum_ += p[0] * p[0]
		return sum_


class Solution:

	def minValue(self, arr, k):
		dict = {}
		for i in arr:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		value = list(dict.values())
		for i in range(k):
			val = value.index(max(value))
			value[val] = value[val] - 1
		return sum([i ** 2 for i in value])


class Solution:

	def minValue(self, s, k):
		char_dict = {}
		for i in range(0, len(s)):
			if s[i] in char_dict:
				char_dict[s[i]] = char_dict[s[i]] + 1
			else:
				char_dict[s[i]] = 1
		char_values = list(char_dict.values())
		char_values.sort()
		while k:
			char_values = self.remove_count(char_values)
			k = k - 1
		output = 0
		for value in char_values:
			output = output + value ** 2
		return output

	def remove_count(self, char_values):
		char_values.sort()
		char_values[-1] = char_values[-1] - 1
		return char_values


class Solution:

	def minValue(self, s, k):
		res = [0 for _ in range(26)]
		n = len(s)
		for i in range(n):
			res[97 - ord(s[i])] += 1
		loop = k
		i = 25
		while loop > 0:
			res.sort()
			flag = False
			if res[i] == 0:
				break
			if res[i] != res[i - 1] and loop > 0:
				flag = True
				loop -= 1
				res[i] -= 1
			if not flag and loop > 0:
				loop -= 1
				res[i] -= 1
		ans = 0
		for i in range(26):
			ans += res[i] * res[i]
		return ans


class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		for i in d:
			l.append(d[i])
		l.sort()
		while k > 0:
			l[-1] -= 1
			k -= 1
			l.sort()
		su = 0
		for i in l:
			su = su + i ** 2
		return su


from queue import PriorityQueue
max_char = 26

class Solution:

	def minValue(self, s, k):
		l = len(s)
		if k > l:
			return 0
		freq = [0] * max_char
		for i in range(l):
			freq[ord(s[i]) - 97] += 1
		q = PriorityQueue()
		for i in range(max_char):
			q.put(-freq[i])
		while k > 0:
			temp = q.get()
			temp = temp + 1
			q.put(temp, temp)
			k = k - 1
		ans = 0
		while not q.empty():
			temp = q.get()
			temp = temp * -1
			ans += temp * temp
		return ans


from collections import Counter
import heapq

class Solution:

	def minValue(self, s, k):
		c = Counter(s)
		heap = [-item for item in c.values()]
		heapq.heapify(heap)
		for _ in range(k):
			item = heapq.heappop(heap)
			item = item + 1
			heapq.heappush(heap, item)
		sum1 = 0
		for item in heap:
			sum1 += item ** 2
		return sum1


import heapq

class Solution:

	def minValue(self, s, k):
		f = [0] * 26
		for c in s:
			f[ord(c) - 97] += 1
		f = [-i for i in f]
		heapq.heapify(f)
		while k:
			top = -heapq.heappop(f)
			if top == 0:
				break
			top -= 1
			heapq.heappush(f, -top)
			k -= 1
		return sum((i * i for i in f))


import heapq

class Solution:

	def minValue(self, s, k):
		h = [0] * 26
		for i in s:
			h[ord(i) - 97] += 1
		q = []
		for i in range(len(h)):
			if h[i] != 0:
				q.append(-1 * h[i])
		heapq.heapify(q)
		ans = 0
		while k:
			top = heapq.heappop(q)
			top = -1 * (abs(top) - 1)
			k -= 1
			heapq.heappush(q, top)
		while len(q) != 0:
			top = q.pop(0)
			ans += top * top
		return ans


class Solution:

	def minValue(self, s, k):
		d = [0] * 26
		for i in range(len(s)):
			d[ord(s[i]) - ord('a')] += 1
		d.sort()
		while k > 0:
			d[-1] -= 1
			d.sort()
			k -= 1
		ans = 0
		for i in range(26):
			ans += d[i] * d[i]
		return ans


class Solution:

	def minValue(self, s, k):
		d = {}
		ans = 0
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = list(d.values())
		while k != 0:
			l.sort(reverse=True)
			l[0] = l[0] - 1
			k -= 1
		for j in l:
			ans += j * j
		return ans


import heapq

class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			d[i] = d.get(i, 0) + 1
		q = []
		for i in list(d.values()):
			heapq.heappush(q, -i)
		for i in range(k):
			temp = -1 * heapq.heappop(q)
			temp -= 1
			heapq.heappush(q, -temp)
		return sum([i * i for i in q])


class Solution:

	def minValue(self, s, k):
		letter_freq = {}
		for ch in s:
			letter_freq[ch] = letter_freq[ch] + 1 if ch in letter_freq else 1
		for i in range(k):
			most_freq = max(letter_freq, key=letter_freq.get)
			letter_freq[most_freq] -= 1
		return sum([freq ** 2 for freq in letter_freq.values()])


class Solution:

	def minValue(self, s, k):
		letter_frequencies = {}
		for ch in s:
			if ch not in letter_frequencies:
				letter_frequencies[ch] = 1
			else:
				letter_frequencies[ch] = letter_frequencies[ch] + 1
		for i in range(k):
			most_freq = max(letter_frequencies, key=letter_frequencies.get)
			letter_frequencies[most_freq] = letter_frequencies[most_freq] - 1
		sum_of_squares = 0
		for freq in letter_frequencies.values():
			sum_of_squares = sum_of_squares + freq ** 2
		return sum_of_squares


class Solution:

	def minValue(self, s, k):
		d = {}
		for i in range(len(s)):
			j = s[i]
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
		while k:
			s = 0
			value = 0
			for (key, val) in d.items():
				if val > value:
					value = val
					s = key
			d[s] = d[s] - 1
			k = k - 1
		ans = 0
		for (key, val) in d.items():
			ans = ans + val ** 2
		return ans


class Solution:

	def minValue(self, s, k):
		ourhash = {}
		for i in s:
			if i in ourhash:
				ourhash[i] += 1
			else:
				ourhash[i] = 1
		ourList = []
		for i in ourhash:
			ourList.append(ourhash[i])
		ourList.sort(reverse=True)
		h = len(ourList)
		while k > 0:
			cur_Val = ourList[0]
			for i in range(h):
				if k <= 0:
					break
				elif cur_Val == ourList[i]:
					ourList[i] -= 1
					k -= 1
				else:
					break
		finalAnswer = 0
		for i in ourList:
			finalAnswer += i ** 2
		return finalAnswer


from heapq import *
from collections import Counter

class Solution:

	def minValue(self, s, k):
		heap = []
		for x in Counter(s).values():
			heappush(heap, -x)
		while k:
			heappush(heap, heappop(heap) + 1)
			k -= 1
		return sum((x * x for x in heap))


from collections import Counter
from queue import PriorityQueue

class Solution:

	def minValue(self, s, k):
		if k >= len(s):
			return 0
		c = Counter(s)
		pq = PriorityQueue()
		for freq in c.values():
			pq.put(-freq)
		while k > 0:
			most_freq = pq.get()
			if most_freq < -1:
				pq.put(most_freq + 1)
			k -= 1
		sq_sum = 0
		while not pq.empty():
			sq_sum += pq.get() ** 2
		return sq_sum


from heapq import heappush, heappop

class Solution:

	def minValue(self, s, k):
		h = []
		d = {}
		ans = 0
		for i in s:
			d[i] = d.get(i, 0) + 1
		for i in d:
			heappush(h, -d[i])
		while k:
			val = heappop(h)
			heappush(h, val + 1)
			k -= 1
		while h:
			freq = -heappop(h)
			ans += freq * freq
		return ans


class Solution:

	def minValue(self, s, k):
		freq = [0] * 26
		result = 0
		for i in s:
			freq[ord(i) - ord('a')] += 1
		freq.sort(reverse=True)
		while k:
			freq[0] -= 1
			freq.sort(reverse=True)
			k -= 1
		result = sum(map(lambda i: i * i, freq))
		return result


import heapq

class Solution:

	def minValue(self, s, k):
		arr = []
		hashmap = {}
		for i in range(len(s)):
			if s[i] not in hashmap:
				hashmap[s[i]] = 1
			else:
				hashmap[s[i]] += 1
		for (ch, f) in hashmap.items():
			arr.append((-f, ch))
		heapq.heapify(arr)
		i = 0
		while i < k:
			(freq, c) = heapq.heappop(arr)
			freq += 1
			heapq.heappush(arr, (freq, c))
			i += 1
		sumv = 0
		for x in arr:
			sumv += x[0] ** 2
		return sumv


class Solution:

	def minValue(self, s, k):
		d = dict()
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		m = list(d.values())
		for i in range(k):
			a = m.index(max(m))
			m[a] -= 1
		b = 0
		for i in m:
			b += i * i
		return b


import heapq as hq
import collections as coll

class Solution:

	def minValue(self, s, k):
		freq = coll.Counter(s)
		mxh = [-cnt for cnt in freq.values()]
		hq.heapify(mxh)
		for _ in range(k):
			cnt = hq.heappop(mxh)
			cnt += 1
			if cnt < 0:
				hq.heappush(mxh, cnt)
		ans = 0
		while mxh:
			cnt = hq.heappop(mxh)
			ans += cnt * cnt
		return ans


from collections import Counter
import heapq

class Solution:

	def minValue(self, s, k):
		d = Counter(s)
		d1 = sorted(d.values())
		heapq.heapify(d1)
		c = 0
		while c != k and d1 != []:
			a = max(d1)
			d1.remove(a)
			a = a - 1
			d1.append(a)
			c += 1
		tot = 0
		for i in d1:
			tot += i ** 2
		return tot


class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		x = []
		for i in d:
			x.append(d[i])
		while k > 0:
			x.sort(reverse=True)
			x[0] = x[0] - 1
			k -= 1
		ans = 0
		for i in x:
			ans += i * i
		return ans


from heapq import *

class Solution:

	def minValue(self, s, k):
		map = {}
		for i in s:
			map[i] = map.get(i, 0) + 1
		pq = [(-val, key) for (key, val) in map.items()]
		heapify(pq)
		while k:
			(top_val, top_key) = heappop(pq)
			if top_val < 0:
				heappush(pq, (top_val + 1, top_key))
			k -= 1
		ans = 0
		for (val, _) in pq:
			ans += val ** 2
		return ans


import heapq

class Solution:

	def minValue(self, s, k):
		freq = {}
		for ch in s:
			freq[ch] = 1 + freq.get(ch, 0)
		pair = []
		for (ch, v) in freq.items():
			pair.append((-v, ch))
		heapq.heapify(pair)
		while pair and k:
			(v, char) = heapq.heappop(pair)
			v += 1
			k -= 1
			heapq.heappush(pair, (v, char))
		ans = 0
		while pair:
			(v, k) = heapq.heappop(pair)
			ans += v ** 2
		return ans


from collections import Counter
import heapq as hp

class Solution:

	def minValue(self, s, k):
		d = Counter(s)
		arr = []
		hp.heapify(arr)
		for (key, val) in d.items():
			hp.heappush(arr, [-val, key])
		while k > 0:
			a = hp.heappop(arr)
			a[0] += 1
			if a[0]:
				hp.heappush(arr, a)
			k -= 1
		ans = 0
		while len(arr) > 0:
			ans += arr[0][0] * arr[0][0]
			a = hp.heappop(arr)
		return ans


from collections import Counter
from functools import reduce

class Solution:

	def minValue(self, s, k):
		h = Counter(s)
		l = []
		for val in h.values():
			l.append(val)
		while k > 0:
			max_ind = l.index(max(l))
			ele = l.pop(max_ind)
			l.append(ele - 1)
			k -= 1
		l = list(map(lambda a: a ** 2, l))
		sum = reduce(lambda a, b: a + b, l)
		return sum


class Solution:

	def minValue(self, s, k):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		a = list(d.values())
		while k != 0:
			a.sort(reverse=True)
			a[0] = a[0] - 1
			k -= 1
		s = 0
		for i in a:
			s += i ** 2
		return s


from queue import PriorityQueue
MAX_CHAR = 26

class Solution:

	def minValue(self, s, k):
		l = len(s)
		f = [0] * MAX_CHAR
		for i in range(0, l):
			f[ord(s[i]) - 97] += 1
		q = PriorityQueue()
		for i in range(0, 26):
			q.put(-f[i])
		while k > 0:
			temp = q.get()
			temp += 1
			q.put(temp, temp)
			k -= 1
		r = 0
		while not q.empty():
			t = q.get()
			t = t * -1
			r += t * t
		return r


class Solution:

	def minValue(self, s, k):
		dic = {}
		for i in s:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		lis = list(dic.values())
		lis.sort(reverse=True)
		while k != 0:
			lis[0] = lis[0] - 1
			lis.sort(reverse=True)
			k -= 1
		return sum([q * q for q in lis])


from collections import defaultdict
import heapq

class Solution:

	def minValue(self, s, k):
		heap = []
		d = defaultdict(int)
		for i in s:
			d[i] += 1
		for (i, j) in d.items():
			heap.append((j, i))
		heapq._heapify_max(heap)
		for i in range(k):
			temp = heapq._heappop_max(heap)
			a = temp[0] - 1
			b = temp[1]
			d[b] -= 1
			heap.append((a, b))
			heapq._siftdown_max(heap, 0, len(heap) - 1)
		ans = 0
		for i in d:
			ans += d[i] ** 2
		return ans