Given a string of lowercase alphabets and a number k, the task is to find 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.
For example consider the string “geeks”, here frequencies of characters are g -> 1, e -> 2, k -> 1, s -> 1 and value of the string is 1^{2 }+ 2^{2 }+ 1^{2 }+ 1^{2} = 7
 
Example 1:
Input: S = "abccc", K = 1
Output: 6
Explanation: Remove one 'c', then frequency
will be a -> 1, b -> 1, c -> 2.
1^{2 }+ 1^{2 }+ 2^{2 }= 6
Ã¢â¬â¹Example 2:
Input: S = "aaab", K = 2
Output: 2
Explanation: Remove 2 'a's, then frequency
will be a -> 1, b -> 1.
1^{2 }+ 1^{2}^{ }= 2
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minValue() which takes the string s as inputs and returns the answer.
Expected Time Complexity: O(K*log(|S|))
Expected Auxiliary Space: O(constant)
Constraints:
1 ≤ K, |S| ≤ 10^{4}

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 = {}
		s = 0
		for i in S:
			d[i] = d.get(i, 0) + 1
		v = list(d.values())
		for i in range(k):
			maxValueIndex = v.index(max(v))
			if v[maxValueIndex] == 0:
				return 0
			v[maxValueIndex] = v[maxValueIndex] - 1
		for i in v:
			s += i ** 2
		return s


from queue import PriorityQueue

class Solution:

	def minValue(self, S, K):
		a = []
		b = []
		for i in S:
			if i not in a:
				a.append(i)
				b.append(S.count(i))
		for i in range(K):
			temp = b.index(max(b))
			if b[temp] > 0:
				b[temp] -= 1
		s = 0
		for i in b:
			s += i ** 2
		return s


class Solution:

	def minValue(self, S, K):
		a = []
		b = []
		for i in S:
			if i not in a:
				a.append(i)
				b.append(S.count(i))
		for i in range(k):
			temp = b.index(max(b))
			if b[temp] > 0:
				b[temp] -= 1
		s = 0
		for i in b:
			s += i ** 2
		return s


from collections import Counter

class Solution:

	def minValue(self, S, K):
		c = Counter(S)
		vals = list(c.values())
		while K != 0:
			m = max(vals)
			vals.remove(m)
			vals.append(m - 1)
			if set(vals) == {0}:
				break
			K -= 1
		ct = 0
		for i in vals:
			ct += i * i
		return ct


class Solution:

	def minValue(self, S, K):
		freq = {}
		for i in S:
			try:
				freq[i] = freq.get(i, 0) + 1
			except:
				freq[i] = 1
		values = list(freq.values())
		for i in range(K):
			temp = values.index(max(values))
			if values[temp] > 0:
				values[temp] -= 1
		return sum([i ** 2 for i in values])


class Solution:

	def minValue(self, S, K):
		l1 = list(S)
		list_result = []
		d = {}
		for index in S:
			if index not in d:
				d[index] = 1
			else:
				d[index] += 1
		for index in d.values():
			list_result.append(index)
		for i in range(K):
			temp = list_result.index(max(list_result))
			if list_result[temp] > 0:
				list_result[temp] -= 1
		s = 0
		for index in list_result:
			s += index ** 2
		return s


class Solution:

	def minValue(self, S, K):
		d = dict()
		for i in range(len(S)):
			d[S[i]] = d.get(S[i], 0) + 1
		l = []
		for i in d.values():
			l.append(i)
		for i in range(k):
			temp1 = l.index(max(l))
			if l[temp1] > 0:
				l[temp1] -= 1
		sum = 0
		for i in l:
			sum += i * i
		return sum


class Solution:

	def minValue(self, S, K):
		d = {}
		l = []
		s = 0
		res = ''
		for i in range(len(S)):
			if S[i] not in d:
				d[S[i]] = 1
			else:
				d[S[i]] += 1
		for i in d.values():
			l.append(i)
		for i in range(K):
			temp = l.index(max(l))
			if l[temp] > 0:
				l[temp] -= 1
		s = 0
		for i in l:
			s += i ** 2
		return s


class Solution:

	def minValue(self, S, K):
		counter = {}
		for c in S:
			count = counter.get(c, 0)
			counter[c] = count + 1
		counter = [(i, v) for (i, v) in enumerate(counter.values())]
		while K > 0:
			(i, val) = max(counter, key=lambda v: v[1])
			if val <= 0:
				break
			counter[i] = (i, val - 1)
			K -= 1
		return sum((v[1] * v[1] for v in counter))


class Solution:

	def minValue(self, S, K):
		counter = {}
		for c in S:
			count = counter.get(c, 0)
			counter[c] = count + 1
		counter = [v for v in counter.values()]
		counter.sort(reverse=True)
		if sum(counter) <= K:
			return 0
		while K > 0:
			counter[0] -= 1
			counter.sort(reverse=True)
			K -= 1
		return sum((v * v for v in counter))


class Solution:

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


import collections

class Solution:

	def minValue(self, S, K):
		if K >= len(S):
			return 0
		c = collections.Counter(S)
		stack = sorted(c.values())
		queue = collections.deque()
		for _ in range(K):
			if not stack:
				queue.appendleft(queue.pop() - 1)
			elif queue and queue[-1] >= stack[-1]:
				queue.appendleft(queue.pop() - 1)
			else:
				queue.appendleft(stack.pop() - 1)
		result = 0
		for item in stack:
			result += item ** 2
		while queue:
			result += queue.pop() ** 2
		return result


import heapq

class Solution:

	def minValue(self, S, K):
		d = {}
		for i in S:
			d[i] = 1 + d.get(i, 0)
		x = []
		for i in d:
			x.append(-1 * d[i])
		heapq.heapify(x)
		for i in range(K):
			if not x:
				break
			a = -1 * heapq.heappop(x)
			c = abs(a) - 1
			if c == 0:
				pass
			else:
				heapq.heappush(x, -c)
		ans = 0
		for i in x:
			ans += abs(i) * abs(i)
		return ans


class Solution:

	def minValue(self, strg, k):
		from collections import defaultdict
		d = defaultdict(int)
		for i in strg:
			d[i] += 1
		import heapq
		heap = []
		for i in d.values():
			heapq.heappush(heap, -i)
		while k > 0 and heap:
			curr = heapq.heappop(heap)
			curr += 1
			k -= 1
			if curr < 0:
				heapq.heappush(heap, curr)
		total = 0
		while heap:
			total += (-heapq.heappop(heap)) ** 2
		return total


class Solution:

	def minValue(self, S, K):
		d = {}
		for i in S:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		l = []
		for i in d:
			l.append(d[i])
		for i in range(K):
			if len(l) > 0:
				m = max(l)
				l.remove(m)
			if m - 1 >= 0:
				l.append(m - 1)
		res = 0
		for i in l:
			res += i * i
		return res


import heapq

class Solution:

	def minValue(self, S, k):
		d = {}
		for char in S:
			d[char] = d.get(char, 0) + 1
		vals = [num * -1 for num in d.values()]
		heapq.heapify(vals)
		while k and vals:
			curr = heapq.heappop(vals)
			if vals:
				top = vals[0]
				diff = min(k, top - curr + 1)
				if curr + diff < 0:
					heapq.heappush(vals, curr + diff)
				k -= diff
			elif k + curr < 0:
				heapq.heappush(vals, curr + k)
				k = 0
		ans = sum((num ** 2 for num in vals))
		return ans


class Solution:

	def minValue(self, S, K):
		result = 0
		counts = [S.count(i) for i in set(S)]
		for i in range(K):
			if max(counts):
				counts[counts.index(max(counts))] -= 1
		for i in counts:
			result += i ** 2
		return result


class Solution:

	def minValue(self, S, K):
		if len(S) <= K:
			return 0
		S = [list(S)]
		S.append(list(set(S[0])))
		S.append([S[0].count(i) for i in S[1]])
		while K != 0:
			i = S[2].index(max(S[2]))
			S[2][i] -= 1
			K -= 1
		ans = 0
		for i in S[2]:
			ans += i * i
		return ans


import math

class Solution:

	def minValue(self, S, K):
		if len(S) <= K:
			return 0
		dicts = {}
		for x in S:
			if x in dicts:
				dicts[x] += 1
			else:
				dicts[x] = 1
		values = list(dicts.values())
		values.sort(reverse=True)
		count = 0
		while count != K:
			values[0] = values[0] - 1
			values.sort(reverse=True)
			count = count + 1
		sums = 0
		for j in range(len(values)):
			sums += int(math.pow(values[j], 2))
		return sums


from collections import defaultdict

class Solution:

	def minValue(self, S, K):
		if k > len(S):
			return 0
		sum1 = 0
		count = []
		dict1 = defaultdict()
		for i in S:
			dict1[i] = S.count(i)
		for value in dict1.values():
			count.append(value)
		while K:
			m = max(count)
			count.remove(m)
			m = m - 1
			count.append(m)
			K = K - 1
		for i in range(len(count)):
			sum1 += count[i] * count[i]
		return sum1


from collections import defaultdict

class Solution:

	def minValue(self, S, K):
		if k > len(S):
			return 0
		sum1 = 0
		count = []
		dict1 = defaultdict()
		for i in S:
			dict1[i] = S.count(i)
		for (key, value) in dict1.items():
			dict1[key] = value
			count.append(value)
		count.sort(reverse=True)
		while K:
			m = max(count)
			count.remove(m)
			m = m - 1
			count.append(m)
			K = K - 1
		for i in range(len(count)):
			sum1 += count[i] * count[i]
		return sum1


from collections import defaultdict

class Solution:

	def minValue(self, S, K):
		dic = defaultdict(int)
		for i in S:
			dic[i] += 1
		while K > 0:
			mx = S[0]
			for i in dic.keys():
				if dic[i] > dic[mx]:
					mx = i
			dic[mx] = dic[mx] - 1 if dic[mx] - 1 > 0 else 0
			K -= 1
		value = 0
		for i in dic.keys():
			value += dic[i] ** 2
		return value


from collections import defaultdict

class Solution:

	def minValue(self, S, K):
		d = defaultdict(int)
		for s in S:
			d[s] += 1
		dd = list(d.values())
		for i in range(K):
			id = dd.index(max(dd))
			if dd[id] > 0:
				dd[id] -= 1
		return sum((i ** 2 for i in dd))


import string

class Solution:

	def minValue(self, S, K):
		str_list = [i for i in S]
		cnt_list = list()
		ascii_str = [i for i in string.ascii_lowercase]
		for i in ascii_str:
			if i in S:
				cnt_list.append(S.count(i))
		for i in range(K):
			if max(cnt_list) == 0:
				return 0
			else:
				cnt_list[cnt_list.index(max(cnt_list))] -= 1
		return sum([i ** 2 for i in cnt_list])


class Solution:

	def minValue(self, S, K):
		from collections import Counter
		d = dict(Counter(S))
		first_values = sorted(list(d.values()))[::-1]
		first_values.append(0)
		diff = []
		for i in range(len(first_values) - 1):
			diff.append(first_values[i] - first_values[i + 1])
		curr_k = 0
		temp = 0
		for i in range(len(diff) - 1):
			temp += diff[i] * (i + 1)
		for i in range(len(diff)):
			if curr_k + diff[i] * (i + 1) <= K:
				for j in range(i + 1):
					first_values[j] -= diff[i]
				curr_k += diff[i] * (i + 1)
			elif curr_k < K:
				rem = K - curr_k
				q = rem // (i + 1)
				r = rem % (i + 1)
				if rem != 1:
					for j in range(i + 1):
						if r > 0:
							first_values[j] = first_values[j] - q - 1
							r -= 1
						else:
							first_values[j] -= q
				else:
					first_values[0] -= rem
				break
			else:
				break
		ans = 0
		for i in first_values:
			ans += i ** 2
		return ans


class Solution:

	def minValue(self, S, K):
		d = dict()
		for i in S:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		l = []
		for i in d:
			l.append(d[i])
		l.sort()
		if K >= len(S):
			return 0
		while K:
			if l[-1] == 0:
				l.pop()
			l[-1] = l[-1] - 1
			l.sort()
			K -= 1
		c = 0
		for i in l:
			c += i * i
		return c


import heapq

class Solution:

	def minValue(self, S, K):
		heap = []
		d = {}
		for ch in S:
			if ch in d:
				d[ch] += 1
			else:
				d[ch] = 1
		for key in d.keys():
			heapq.heappush(heap, [-d[key], key])
		for i in range(K):
			if len(heap) > 0:
				top = heapq.heappop(heap)
				top[0] = -top[0] - 1
				if top[0] > 0:
					heapq.heappush(heap, [-top[0], top[1]])
			else:
				return 0
		ans = 0
		for curr in heap:
			ans += curr[0] ** 2
		return ans


class Solution:

	def minValue(self, S, K):
		from collections import Counter
		c = Counter(S)
		arr = list(c.values())
		while K > 0:
			maxi = max(arr)
			if maxi == 0:
				return 0
			i = arr.index(maxi)
			arr[i] = maxi - 1
			K = K - 1
		sumx = 0
		for i in arr:
			sumx = sumx + i ** 2
		return sumx
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def minValue(self, S, K):
		a = {}
		for i in S:
			a.update({i: S.count(i)})
		arr = list(a.values())
		while K > 0:
			m = max(arr)
			if m == 0:
				return 0
			i = arr.index(m)
			K = K - 1
			arr[i] = m - 1
		sumx = 0
		for i in arr:
			sumx = sumx + i ** 2
		return sumx
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


from collections import defaultdict

class Solution:

	def minValue(self, S, K):
		d = defaultdict(int)
		for s in S:
			d[s] += 1
		dd = list(d.values())
		for i in range(K):
			id = dd.index(max(dd))
			if dd[id] > 0:
				dd[id] -= 1
		return sum((i ** 2 for i in dd))
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def minValue(self, S, K):
		f = dict()
		for i in S:
			f[i] = f.get(i, 0) + 1
		keys = list(f.keys())
		value = list(f.values())
		while K:
			K -= 1
			x = value.index(max(value))
			value[x] -= 1
		for i in range(len(value)):
			if value[i] > 0:
				value[i] = value[i] * value[i]
			else:
				value[i] = 0
		return sum(value)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def getMax(self, count, size):
		max_val = -1
		lst = [0] * 2
		for i in range(size):
			if count[i] > max_val:
				max_val = count[i]
				max_index = i
		lst[0] = max_val
		lst[1] = max_index
		return lst

	def minValue(self, S, K):
		sum = 0
		count = [0] * 26
		size = len(count)
		a = ord('a')
		for ele in S:
			pos = ord(ele) - a
			count[pos] += 1
		for i in range(K):
			res = self.getMax(count, size)
			pos = res[1]
			if res[0] > 0:
				count[pos] = res[0] - 1
		for ele in count:
			sum += ele * ele
		return sum
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def minValue(self, S, K):
		s = set(S)
		ls = []
		for x in s:
			ls.append(S.count(x))
		for i in range(K):
			m = max(ls)
			mi = ls.index(m)
			if m > 0:
				nv = m - 1
				ls[mi] = nv
		su = 0
		for x in ls:
			su += x * x
		return su
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


from queue import PriorityQueue

class Solution:

	def minValue(self, S, k):
		if k >= len(S):
			return 0
		c = [0] * 26
		count = []
		for i in S:
			c[ord(i) - 97] += 1
		q = PriorityQueue()
		for i in range(0, 26):
			q.put(-c[i])
		while k > 0:
			temp = q.get()
			temp = temp + 1
			q.put(temp)
			k = k - 1
		result = 0
		while not q.empty():
			temp = q.get()
			temp = temp * -1
			result += temp * temp
		return result
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def minValue(self, S, K):
		mp = [0] * 26
		for i in S:
			mp[ord(i) - 97] += 1
		m = -1
		n = -1
		for j in range(K):
			for i in range(26):
				if mp[i] > n:
					n = mp[i]
					m = i
			mp[m] = mp[m] - 1
			m = -1
			n = -1
		ans = 0
		for i in range(26):
			if mp[i] > 0:
				ans += mp[i] ** 2
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def minValue(self, S, K):
		dic = {}
		lst = list(S)
		for itr in range(len(lst)):
			if lst[itr] not in dic.keys():
				dic[lst[itr]] = 1
			else:
				dic[lst[itr]] += 1
		while K > 0:
			KeyValue = max(zip(dic.values(), dic.keys()))
			if KeyValue[0] == 0:
				break
			dic[KeyValue[1]] -= 1
			K -= 1
		values = list(dic.values())
		valueofStr = 0
		for itr in range(len(values)):
			valueofStr += values[itr] ** 2
		return valueofStr
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def minValue(self, S, K):
		s = {}
		for i in S:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		for i in range(K):
			m = 0
			for i in s:
				if s[i] > m:
					m = s[i]
					k = i
			s[k] -= 1
			if m == 0:
				return 0
		g = 0
		for i in s:
			g += s[i] * s[i]
		return g
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(s, k) = input().split()
		k = int(k)
		ob = Solution()
		answer = ob.minValue(s, k)
		print(answer)


class Solution:

	def minValue(self, S, K):
		dic = {}
		for i in S:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		y = sorted(dic.items(), key=lambda x: x[1], reverse=True)
		z = []
		for i in y:
			z.append(i[1])
		i = 0
		while K != 0 and i < len(y):
			if z[i] != 0:
				z[i] -= 1
				K -= 1
				z = sorted(z, reverse=True)
			else:
				i += 1
		a = 0
		for i in z:
			a += i ** 2
		return a


class Solution:

	def minValue(self, st, k):
		d = {}
		for i in st:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		d = sorted(d.values(), reverse=True)
		if sum(d) <= k:
			return 0
		while k > 0:
			a = max(d)
			d.remove(max(d))
			a -= 1
			d.append(a)
			k -= 1
		sm = 0
		for i in d:
			sm += i ** 2
		return sm


class Solution:

	def minValue(self, S, K):
		if K > len(S):
			return 0
		d = {}
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		H = heap()
		for i in list(d.values()):
			H.push(i)
		while K:
			H.push(H.pop() - 1)
			K -= 1
		summ = 0
		for i in H.arr[1:]:
			summ += i * i
		return summ

class heap:

	def __init__(self):
		self.arr = [0]
		self.i = 0

	def push(self, data):
		self.arr.append(data)
		self.i += 1
		self.upheapify(self.i)

	def pop(self):
		res = self.arr[1]
		self.arr[1] = self.arr[self.i]
		self.arr.pop()
		self.i -= 1
		self.downheapify(1)
		return res

	def upheapify(self, child):
		if child <= 1:
			return
		parent = child // 2
		if self.arr[parent] < self.arr[child]:
			(self.arr[parent], self.arr[child]) = (self.arr[child], self.arr[parent])
			self.upheapify(parent)

	def downheapify(self, parent):
		child1 = parent * 2
		child2 = child1 + 1
		child = -1
		if child1 == self.i:
			if self.arr[parent] < self.arr[child1]:
				child = child1
		if child2 <= self.i:
			if self.arr[parent] < self.arr[child1]:
				if self.arr[parent] < self.arr[child2]:
					if self.arr[child1] > self.arr[child2]:
						child = child1
					else:
						child = child2
				else:
					child = child1
			elif self.arr[parent] < self.arr[child2]:
				child = child2
		if child != -1:
			(self.arr[parent], self.arr[child]) = (self.arr[child], self.arr[parent])
			self.downheapify(child)


class Solution:

	def minValue(self, S, K):
		if K > len(S):
			return 0
		d = {}
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		L = list(d.values())
		L.sort()
		while K:
			L.append(L.pop() - 1)
			L.sort()
			K -= 1
		summ = 0
		for i in L:
			summ += i * i
		return summ


from collections import Counter as C

class Solution:

	def minValue(self, s, k):
		l = []
		for (i, j) in C(s).items():
			l.append(j)
		while k > 0:
			l.sort()
			if l[-1] > 0:
				l[-1] -= 1
			k -= 1
		return sum(list(map(lambda x: x * x, l)))


class Solution:

	def minValue(self, S, K):
		s1 = 0
		arr1 = [0] * 26
		for i in S:
			arr1[ord(i) - 97] += 1
		for i in range(K):
			j = arr1.index(max(arr1))
			if arr1[j] == 0:
				return 0
			arr1[j] -= 1
		for i in arr1:
			s1 = s1 + i ** 2
		return s1


from collections import Counter
from heapq import heapify, heappush, heappop

class Solution:

	def minValue(self, S, K):
		d = Counter(S)
		heap = [[-val, key] for (key, val) in d.items()]
		heapify(heap)
		while K > 0 and heap:
			(v, k) = heappop(heap)
			v += 1
			if v < 0:
				heappush(heap, [v, k])
			K -= 1
		s = 0
		while heap:
			s += (heappop(heap)[0] * -1) ** 2
		return s


from queue import PriorityQueue

class Solution:

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


class Solution:

	def minValue(self, s, k):
		if len(s) < k:
			return 0
		d = {}
		for ch in s:
			if ch not in d:
				d[ch] = 1
			else:
				d[ch] += 1
		l1 = list(d.values())
		while k > 0:
			l1.sort(reverse=True)
			l1[0] = l1[0] - 1
			k -= 1
		total = 0
		for x in l1:
			total += x ** 2
		return total


from queue import PriorityQueue

class Solution:

	def minValue(self, S, K):
		if K > len(s):
			return 0
		frequencyMap = [0] * 256
		for i in S:
			frequencyMap[ord(i) - ord('a')] += 1
		priorityQueue = PriorityQueue()
		for i in range(0, 256):
			priorityQueue.put(-frequencyMap[i])
		while K > 0:
			temp = priorityQueue.get()
			temp += 1
			priorityQueue.put(temp, temp)
			K -= 1
		value = 0
		while not priorityQueue.empty():
			temp = priorityQueue.get()
			value += temp * temp
		return value


class Solution:

	def minValue(self, S, K):
		if K >= len(S):
			return 0
		hist = [0] * 26
		for char in S:
			hist[ord(char) - 97] += 1
		while K:
			hist[hist.index(max(hist))] -= 1
			K -= 1
		ans = 0
		for i in range(26):
			ans += hist[i] ** 2
		return ans


class Solution:

	def minValue(self, S, K):
		l = [0] * 26
		for i in S:
			l[ord(i) - 97] += 1
		for _ in range(K):
			index = 0
			for i in range(26):
				if l[i] > l[index]:
					index = i
			l[index] -= 1
		s = 0
		for i in l:
			if i > 0:
				s += i * i
		return s


class Solution:

	def minValue(self, S, K):
		d = {}
		s = 0
		if K > len(S):
			return 0
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		li = list(d.values())
		d = {}
		for i in range(K):
			m = max(li)
			li[li.index(m)] -= 1
		for i in li:
			s += i * i
		return s


class Solution:

	def minValue(self, S, K):
		if K >= len(S):
			return 0
		h = [0] * 26
		for i in S:
			h[ord(i) - 97] += 1
		while K:
			h[h.index(max(h))] -= 1
			K = K - 1
		a = 0
		for i in range(26):
			a = a + h[i] ** 2
		return a


from collections import Counter

class Solution:

	def minValue(self, S, K):
		while K != 0 and S:
			countsdict = Counter(S)
			maxval = max(countsdict.values())
			maxlist = [i for (i, j) in countsdict.items() if j == maxval]
			for ind in range(len(S)):
				if S[ind] in maxlist:
					S = S[:ind] + S[ind + 1:]
					K -= 1
					break
		minsumval = sum([item ** 2 for item in Counter(S).values()])
		return minsumval


class Solution:

	def minValue(self, a, k):
		d = {}
		for i in a:
			d[i] = d.get(i, 0) + 1
		alphabets_count = sorted(d.values(), reverse=True)
		d = {}
		for i in alphabets_count:
			d[i] = d.get(i, 0) + 1
		for i in range(k):
			if alphabets_count[0] > 0:
				d[alphabets_count[0] - 1] = d.get(alphabets_count[0] - 1, 0) + 1
				temp = d[alphabets_count[0]]
				d[alphabets_count[0]] -= 1
				(alphabets_count[0], alphabets_count[temp - 1]) = (alphabets_count[temp - 1], alphabets_count[0] - 1)
		res = 0
		for i in alphabets_count:
			res += i ** 2
		return res


class Solution:

	def minValue(self, S, K):
		dic = {}
		for i in S:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		values = list(dic.values())
		while K > 0:
			values[values.index(max(values))] -= 1
			K -= 1
		ans = 0
		for i in values:
			if i > 0:
				ans += i ** 2
		return ans