Given a string s consisting only lower case alphabets, find the minimum number of changes required to it so that all substrings of the string become distinct.
Note: length of the string is at most 26.
Example 1:
Input: S = "aab"
Output: 1
Explanation: If we change one instance 
of 'a' to any character from 'c' to 'z', 
we get all distinct substrings.
Ã¢â¬â¹Example 2:
Input: S = "ab"
Output: 0
Explanation: As no change is required
hence 0.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minChange() which takes the string S as inputs and returns the answer.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(26)
Constraints:
1 ≤ |S| ≤ 26

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def minChange(self,S):

        # Code here

Solutions:
class Solution:

	def minChange(self, S):
		arr = []
		arr1 = []
		for i in S:
			if i not in arr:
				arr.append(i)
			else:
				arr1.append(i)
		return len(arr1)


class Solution:

	def minChange(self, S):
		freq = [0] * 26
		for i in S:
			freq[ord(i) - ord('a')] += 1
		c = 0
		for i in freq:
			if i > 1:
				c += i - 1
		return c


class Solution:

	def minChange(self, S):
		a = len(set(S))
		b = len(S)
		return b - a


class Solution:

	def minChange(self, S):
		return len(S) - len(set(S))


class Solution:

	def minChange(self, S):
		a = dict()
		for i in S:
			if i not in a:
				a[i] = 1
			else:
				a[i] += 1
		sum = 0
		for i in a:
			if a[i] != 1:
				sum += a[i] - 1
		return sum


class Solution:

	def minChange(self, S):
		lt = list(S)
		st = []
		count = 0
		if len(S) > 26:
			return -1
		for i in lt:
			if i not in st:
				st.append(i)
			else:
				count += 1
		return count


class Solution:

	def minChange(self, S):
		n = len(S)
		sett = list(set(S))
		m = len(sett)
		return n - m


class Solution:

	def minChange(self, S):
		n = len(S)
		c = 0
		S = ''.join(sorted(S))
		for i in range(1, n):
			if S[i] == S[i - 1]:
				c += 1
		return c


class Solution:

	def minChange(self, S):
		a = []
		count = 0
		for i in S:
			if i not in a:
				if S.count(i) > 1:
					count += S.count(i) - 1
					a.append(i)
		return count


class Solution:

	def minChange(self, S):
		a = ''
		for i in S:
			if i not in a:
				a += i
		if len(a) == len(S):
			return 0
		else:
			return len(S) - len(a)


class Solution:

	def minChange(self, S):
		c = set(S)
		if len(S) == len(c):
			return 0
		else:
			return abs(len(S) - len(c))


class Solution:

	def minChange(self, s):
		u = list(set(s))
		return len(s) - len(u)


class Solution:

	def minChange(self, S):
		dct = {}
		for i in S:
			if dct.get(i):
				dct[i] += 1
			else:
				dct[i] = 1
		alpha = 26
		for (key, value) in dct.items():
			alpha -= value
		if alpha > -1:
			return 26 - alpha - len(dct)
		return 0


class Solution:

	def minChange(self, S):
		dct = set()
		for i in S:
			dct.add(i)
		total_alpha = 26
		total_alpha -= len(S)
		if total_alpha > -1:
			return 26 - total_alpha - len(dct)
		return 0


class Solution:

	def minChange(self, S):
		dct = {}
		for i in S:
			if dct.get(i):
				dct[i] += 1
			else:
				dct[i] = 1
		total_alpha = 26
		total_alpha -= len(S)
		if total_alpha > -1:
			return 26 - total_alpha - len(dct)
		return 0


class Solution:

	def minChange(self, S):
		a = ''
		c = 0
		for i in range(len(S)):
			if S[i] not in a:
				a += S[i]
			else:
				c += 1
		return c


class Solution:

	def minChange(self, S):
		l1 = len(S)
		s = set(S)
		l = len(s)
		return l1 - l


class Solution:

	def minChange(self, S):
		res = ''
		count = 0
		for x in S:
			if x not in res:
				res += x
		return len(S) - len(res)


class Solution:

	def minChange(self, S):
		count = 0
		li = [0] * 26
		for i in range(len(S)):
			li[ord(S[i]) - ord('a')] += 1
		for i in range(len(li)):
			if li[i] > 1:
				count += li[i] - 1
		return count


class Solution:

	def minChange(self, s):
		dic = {}
		res = 0
		for elm in s:
			if elm in dic:
				res += 1
			else:
				dic[elm] = 1
		return res


class Solution:

	def minChange(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		c = 0
		for i in d:
			c += d[i] - 1
		return c


class Solution:

	def minChange(self, S):
		c = 0
		S1 = list(S)
		S2 = set(S1)
		for i in S2:
			if S.count(i) > 1:
				c = c + (S.count(i) - 1)
		return c


class Solution:

	def minChange(self, S):
		count1 = 0
		for a in range(0, len(S)):
			for b in range(a + 1, len(S)):
				if S[a] == S[b]:
					count1 += 1
					S = S[:a] + '0' + S[a + 1:]
		if count1 > 0:
			return count1
		else:
			return '0'


class Solution:

	def minChange(self, S):
		l1 = []
		l2 = []
		for i in S:
			if i not in l1:
				l1.append(i)
			else:
				l2.append(i)
		return len(l2)


class Solution:

	def minChange(self, S):
		b = ''
		for i in S:
			if i not in b:
				b = b + i
		return len(S) - len(b)


class Solution:

	def minChange(self, S):
		changeCount = 0
		distinctChar = set(S)
		for i in distinctChar:
			if S.count(i) == 1:
				pass
			else:
				changeCount += S.count(i) - 1
		return changeCount


class Solution:

	def minChange(self, S):
		s = set(S)
		if len(S) == len(s):
			return 0
		else:
			return len(S) - len(s)


class Solution:

	def minChange(self, S):
		D = {}
		k = 0
		for i in S:
			if i not in D:
				D[i] = 1
			else:
				D[i] += 1
		for i in D:
			k += D[i] - 1
		return k


class Solution:

	def minChange(self, S):
		d = {}
		for x in S:
			if x not in d:
				d[x] = 0
			d[x] += 1
		count = 0
		for x in d:
			if d[x] > 1:
				count += d[x] - 1
		return count


class Solution:

	def minChange(self, S):
		l1 = []
		c = 0
		for i in S:
			if i not in l1:
				l1.append(i)
			else:
				c += 1
		return c


class Solution:

	def minChange(self, S):
		c = 0
		s = set(S)
		for i in s:
			if S.count(i) > 1:
				c += S.count(i) - 1
		return c


class Solution:

	def minChange(self, S):
		a = list(S)
		p = set(a)
		return len(a) - len(p)


class Solution:

	def minChange(self, S):
		ls = [0] * 26
		for i in S:
			ls[97 - ord(i)] += 1
		ans = 0
		for i in ls:
			if i > 1:
				ans = ans + i - 1
		return ans


class Solution:

	def minChange(self, S):
		d = {}
		s = 0
		for i in range(len(S)):
			if S[i] in d:
				d[S[i]] = d[S[i]] + 1
			else:
				d[S[i]] = 1
		l = list(d.values())
		for i in range(len(l)):
			if l[i] > 1:
				s = s + l[i] - 1
			else:
				pass
		return s


class Solution:

	def minChange(self, S):
		dic = {}
		ans = 0
		for ch in S:
			if ch in dic:
				ans += 1
			else:
				dic[ch] = 1
		return ans


class Solution:

	def minChange(self, S):
		m = {}
		c = 0
		for i in S:
			if i in m:
				c += 1
			else:
				m[i] = 1
		return c


class Solution:

	def minChange(self, S):
		dis = {}
		for x in S:
			if x in dis:
				dis[x] += 1
			else:
				dis[x] = 1
		vals = sum([x for x in dis.values()])
		counts = len(set(S))
		return vals - counts


class Solution:

	def minChange(self, S):
		l = len(S)
		d = ''.join(set(S))
		l1 = len(d)
		return l - l1


class Solution:

	def minChange(self, S):
		dic = {}
		for i in S:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		c = 0
		for j in dic:
			if dic[j] > 1:
				c += dic[j] - 1
		return c


class Solution:

	def minChange(self, str):
		MAX_CHAR = [26]
		n = len(str)
		if n > MAX_CHAR[0]:
			return -1
		dist_count = 0
		count = [0] * MAX_CHAR[0]
		for i in range(n):
			if count[ord(str[i]) - ord('a')] == 0:
				dist_count += 1
			count[ord(str[i]) - ord('a')] += 1
		return n - dist_count


class Solution:

	def minChange(self, S):
		r = []
		x = 0
		for i in S:
			if i not in r:
				r.append(i)
			else:
				x = x + 1
		return x
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.minChange(S))


class Solution:

	def minChange(self, S):
		s = set(S)
		if len(S) == len(s):
			return 0
		else:
			return len(S) - len(s)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.minChange(S))


class Solution:

	def minChange(self, S):
		count = 0
		freq = [0] * 26
		for i in S:
			freq[ord(i) - 97] += 1
		for i in freq:
			if i > 1:
				count = count + i - 1
		return count


class Solution:

	def minChange(self, S):
		same = 0
		for i in range(len(S)):
			if S[i] in S[i + 1:]:
				same += 1
		return same


class Solution:

	def minChange(self, S):
		n = len(S)
		stack = []
		minc = 0
		for i in S:
			if i not in stack:
				stack.append(i)
			else:
				minc += 1
		return minc


class Solution:

	def minChange(self, S):
		d = {}
		for i in S:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		c = 0
		for i in d:
			if d[i] > 1:
				c += d[i] - 1
		return c


class Solution:

	def minChange(self, S):
		d = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
		n = [0] * 26
		for i in S:
			n[d[i]] = n[d[i]] + 1
		count = 0
		for i in n:
			if i > 1:
				count = count + (i - 1)
		return count


class Solution:

	def minChange(self, S):
		if len(S) > 26:
			return -1
		alpha = dict()
		for i in S:
			if i in alpha:
				alpha[i] += 1
			else:
				alpha[i] = 1
		count = 0
		for (k, v) in alpha.items():
			if v > 1:
				count += v - 1
		return count


class Solution:

	def minChange(self, S):
		r = len(S)
		d = {}
		for k in S:
			d[k] = d.get(k, 0) + 1
		s = 0
		u = []
		for (x, y) in d.items():
			if y > 1:
				u.append(y)
		for i in range(len(u)):
			s = s + u[i] - 1
		return s


class Solution:

	def minChange(self, S):
		uniquechars = set(S)
		uniquechars_length = len(uniquechars)
		S_length = len(S)
		if S_length == uniquechars_length:
			return 0
		return S_length - uniquechars_length


class Solution:

	def minChange(self, S):
		l = []
		cnt = 0
		for char in S:
			if char not in l:
				l.append(char)
			else:
				cnt += 1
		return cnt


class Solution:

	def minChange(self, S):
		if sorted(list(set(S))) == list(S):
			return 0
		else:
			return len(S) - len(set(S))


from collections import Counter

class Solution:

	def minChange(self, S):
		dic = Counter(S)
		del_count = 0
		for val in dic.values():
			if val != 1:
				del_count += val - 1
		return del_count


class Solution:

	def minChange(self, S):
		res = 0
		lst = [0] * 26
		for i in S:
			lst[ord(i) - 97] += 1
		for i in lst:
			if i > 1:
				res += i - 1
		return res


class Solution:

	def minChange(self, S):
		d = dict().fromkeys(S, 0)
		c = 0
		for j in S:
			if d[j] == 0:
				d[j] += 1
			else:
				c += 1
		return c


class Solution:

	def minChange(self, S):
		hm = {}
		for ch in S:
			hm[ch] = hm.get(ch, 0) + 1
		return len(S) - len(hm)


class Solution:

	def minChange(self, S):
		s = set()
		count = 0
		for i in range(len(S)):
			if S[i] in s:
				count += 1
			else:
				s.add(S[i])
		return count


class Solution:

	def minChange(self, S):
		a = len(S)
		di = {}
		for i in S:
			di[i] = di.get(i, 0) + 1
		l = len(di)
		return a - l


class Solution:

	def minChange(self, S):
		a = list(S)
		b = []
		for i in a:
			if i in b:
				pass
			else:
				b.append(i)
		d = len(a) - len(b)
		return d


class Solution:

	def minChange(self, S):
		d = {chr(i): 0 for i in range(97, 123)}
		for i in S:
			d[i] += 1
		k = max(d.values())
		if k > 1:
			count = 0
			for i in d.values():
				if i > 1:
					count += i - 1
			return count
		return 0


class Solution:

	def minChange(self, S):
		dict1 = {}
		count = 0
		for i in S:
			dict1[i] = 0
		for i in S:
			if dict1[i] == 1:
				count += 1
			else:
				dict1[i] = 1
		return count


class Solution:

	def minChange(self, S):
		count = 0
		S = sorted(S)
		for i in range(len(S) - 1):
			if S[i] == S[i + 1]:
				count += 1
			else:
				pass
		return count


class Solution:

	def minChange(self, S):
		c = 0
		l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
		for i in S:
			if i in l:
				l.remove(i)
			else:
				c += 1
		return c


from collections import Counter

class Solution:

	def minChange(self, S):
		count = 0
		d = Counter(S)
		for (i, j) in d.items():
			if j > 1:
				count += j - 1
		return count


class Solution:

	def minChange(self, S):
		hm = {}
		cnt = 0
		for ele in S:
			if ele in hm:
				hm[ele] += 1
			else:
				hm[ele] = 1
		for ele in hm:
			if hm[ele] > 1:
				cnt += hm[ele] - 1
		return cnt