Given a string containing lower and uppercase alphabets, the task is to find the maximum number of characters between any two same (case sensitivity) character in the string. 
Example 1:
Input:
S = "socks"
Output: 3
Explanation: There are 3 characters between
the two occurrences of 's'.
Example 2:
Input: 
S = "FoR"
Output: -1
Explanation: No repeating character present.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxChars() which takes the string S as input and returns the maximum number of characters between any two same characters in the string.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|S|<=10^{5}

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:

    def maxChars(self, s):
        # code here

Solutions:
class Solution:

	def maxChars(self, s):
		d = {}
		for i in range(len(s)):
			if s[i] in d:
				d[s[i]].append(i)
			else:
				d[s[i]] = [i]
		mx = -1
		for i in d:
			t = d[i][-1] - d[i][0] - 1
			if t > mx:
				mx = t
		return mx


class Solution:

	def maxChars(self, s):
		dic = {}
		mx = -1
		for i in range(len(s)):
			if s[i] not in dic:
				dic[s[i]] = i
			else:
				mx = max(mx, i - dic[s[i]] - 1)
		return mx


class Solution:

	def maxChars(self, s):
		char_counts = {}
		max_count = 0
		for (i, c) in enumerate(s):
			if c in char_counts:
				max_count = max(max_count, i - char_counts[c])
			else:
				char_counts[c] = i
		return max_count - 1


class Solution:

	def maxChars(self, s):
		letterArr = []
		obj = {}
		for i in range(len(s)):
			if s[i] not in letterArr:
				letterArr.append(s[i])
			else:
				obj[s[i]] = i - int(s.index(s[i]) + 1)
		valLis = list(obj.values())
		if len(valLis) > 0:
			return max(valLis)
		else:
			return -1


class Solution:

	def maxChars(self, s):
		d = {}
		c = -1
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = i
			else:
				c = max(c, i - d[s[i]] - 1)
		return c


class Solution:

	def maxChars(self, s):
		d = {}
		for i in range(len(s)):
			try:
				d[s[i]].append(i)
			except:
				d[s[i]] = [i]
		count = 0
		checker = 0
		for key in d:
			if len(d[key]) > 1:
				checker += 1
				cur_length = d[key][len(d[key]) - 1] - (d[key][0] + 1)
				if cur_length > count:
					count = cur_length
		if checker == 0:
			return -1
		return count


class Solution:

	def maxChars(self, s):
		d = {}
		d_id = {}
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = -1
				d_id[s[i]] = i
			elif s[i] in d:
				d[s[i]] = max(d[s[i]], i - 1 - d_id[s[i]])
				d_id[s[i]] = i if d_id[s[i]] == -1 else d_id[s[i]]
		d = sorted(d.items(), reverse=True, key=lambda n: n[1])
		if d[0][1] != -1:
			return d[0][1]
		else:
			return -1


class Solution:

	def maxChars(self, s):
		distance = {}
		n = len(s)
		for i in range(n):
			if s[i] in distance:
				distance[s[i]].append(i)
			else:
				distance[s[i]] = [i]
		max_ = -1
		for (k, v) in distance.items():
			if len(v) < 2:
				continue
			max_ = v[-1] - v[0] - 1 if v[-1] - v[0] - 1 > max_ else max_
		return max_


class Solution:

	def maxChars(self, s):
		mapp = {}
		maxi = -1
		for i in range(len(s)):
			if s[i] not in mapp:
				mapp[s[i]] = i
			else:
				maxi = max(maxi, i - mapp[s[i]] - 1)
		return maxi


class Solution:

	def maxChars(self, b):
		res = []
		ans = -1
		for i in range(len(s)):
			if b[i] not in res:
				res.append(b[i])
			else:
				a = b.index(b[i])
				n = len(b[a:i]) - 1
				if n > ans:
					ans = n
		return ans


MAX_CHAR = 256

class Solution:

	def maxChars(self, s):
		d = {}
		maxchar = -1
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = i
			else:
				btw_char = i - d[s[i]] - 1
				maxchar = max(maxchar, btw_char)
		return maxchar


MAX_CHAR = 256

class Solution:

	def maxChars(self, s):
		n = len(s)
		res = -1
		firstInd = [-1 for i in range(MAX_CHAR)]
		for i in range(n):
			first_ind = firstInd[ord(s[i])]
			if first_ind == -1:
				firstInd[ord(s[i])] = i
			else:
				res = max(res, abs(i - first_ind - 1))
		return res


class Solution:

	def maxChars(self, s):
		first = {}
		last = {}
		n = len(s)
		max_diff = -1
		for i in range(n):
			if s[i] not in first:
				first[s[i]] = i
			else:
				last[s[i]] = i
		for key in last:
			diff = last[key] - first[key]
			max_diff = max(max_diff, diff - 1)
		return max_diff


class Solution:

	def maxChars(self, s):
		m = {}
		c = 0
		for i in s:
			if i not in m:
				m[i] = [c, -9999999]
			else:
				m[i][1] = c
			c += 1
		k = -1
		for i in m:
			d = m[i][1] - m[i][0] - 1
			if d > k:
				k = d
		return k


class Solution:

	def maxChars(self, s):
		x = {}
		for i in range(len(s)):
			a = s[i]
			if a not in x:
				x[a] = [i]
			else:
				x[a].append(i)
		m = []
		for i in x:
			b = x[i]
			m.append(b[-1] - b[0])
		return max(m) - 1


class Solution:

	def maxChars(self, s):
		su = s
		k = {}
		for i in range(len(su)):
			if su[i] in k.keys():
				k[su[i]].append(i)
			else:
				k[su[i]] = [i]
		kt = {}
		for i in k.keys():
			kt[i] = max(k[i]) - min(k[i])
		res = max(kt.values())
		return res - 1


class Solution:

	def maxChars(self, s):
		mp = {}
		ln = -1
		for i in range(len(s)):
			if s[i] in mp:
				max_char = i - mp[s[i]] - 1
				ln = max(ln, max_char)
			else:
				mp[s[i]] = i
		return ln


class Solution:

	def maxChars(self, s):
		l = {}
		k = []
		for i in range(len(s)):
			l[s[i]] = []
		for i in range(len(s)):
			l[s[i]].append(i)
		for i in l:
			k.append(max(l[i]) - min(l[i]) - 1)
		return max(k)


class Solution:

	def maxChars(self, s):
		n = len(s)
		temp = set(s)
		srev = s[::-1]
		ans = 0
		for i in temp:
			ans = max(ans, abs(s.index(i) - (n - srev.index(i) - 1)))
		return ans - 1


class Solution:

	def maxChars(self, s):
		c = []
		g = {}
		s.lower()
		for i in s:
			if i not in g:
				g[i] = 1
			else:
				a = s.rindex(i) - s.index(i) - 1
				c.append(a)
		if len(c) == 0:
			return -1
		else:
			return max(c)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		ans = solObj.maxChars(s)
		print(ans)


class Solution:

	def maxChars(self, s):
		d = {}
		maxchar = -1
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = i
			else:
				btw_char = i - d[s[i]] - 1
				maxchar = max(maxchar, btw_char)
		return maxchar
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		ans = solObj.maxChars(s)
		print(ans)


class Solution:

	def maxChars(self, s):
		temp = -1
		for i in s:
			x = s.rfind(i) - s.find(i) - 1
			if x > temp:
				temp = x
		if temp > -1:
			return temp
		else:
			return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		ans = solObj.maxChars(s)
		print(ans)


from collections import defaultdict

class Solution:

	def maxChars(self, s):
		d = defaultdict(int)
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = [0, i + 1]
			else:
				mn = d[s[i]][1]
				d[s[i]] = [i + 1, mn]
		mx = 0
		for i in d.keys():
			temp = d[i][0] - d[i][1]
			mx = max(mx, temp)
		if mx == 0:
			return -1
		return mx - 1


class Solution:

	def maxChars(self, s):
		maxx = -1
		d = {}
		n = len(s)
		for i in range(n):
			if s[i] not in d:
				d[s[i]] = i
			else:
				diff = i - d[s[i]]
				if diff > maxx:
					maxx = diff
		if maxx > -1:
			return maxx - 1
		return -1


from collections import Counter as c

class Solution:

	def maxChars(self, s):
		d = c(s)
		m = -1
		for i in s:
			if d[i] > 1:
				d[i] = 1
				j = len(s) - 1
				while s[j] != i:
					j -= 1
				m = max(j - 1 - s.index(i), m)
		return m


class Solution:

	def maxChars(self, s):
		high = -1
		hash_map = {}
		flag = False
		for i in range(len(s)):
			if s[i] in hash_map.keys():
				hash_map[s[i]].append(i)
				flag = True
			else:
				hash_map[s[i]] = [i]
		if flag == False:
			return high
		for ele in hash_map.keys():
			if len(hash_map[ele]) > 1:
				maxi = hash_map[ele][-1] - (hash_map[ele][0] + 1)
				if maxi > high:
					high = maxi
		return high


class Solution:

	def maxChars(self, s):
		MAX = -1
		dict_ = {}
		N = len(s)
		for i in range(N):
			if s[i] not in dict_:
				dict_[s[i]] = i
			else:
				diff = i - dict_[s[i]]
				if diff > MAX:
					MAX = diff
		if MAX > -1:
			return MAX - 1
		else:
			return -1


class Solution:

	def maxChars(self, s):
		hm = {}
		rm = {}
		for i in range(len(s)):
			if s[i] not in hm.keys():
				hm[s[i]] = i
			else:
				v = i - s.find(s[i]) - 1
				rm[s[i]] = v
		if len(rm) == 0:
			return -1
		r = 0
		for i in rm.values():
			r = max(r, i)
		return r


from collections import Counter as c

class Solution:

	def maxChars(self, s):
		m = -1
		first_index = [-1 for i in range(225)]
		d = c(s)
		for i in range(len(s)):
			start_index = first_index[ord(s[i])]
			if start_index == -1:
				first_index[ord(s[i])] = i
			else:
				m = max(m, i - start_index - 1)
		return m


class Solution:

	def maxChars(self, s):
		c = -1
		d = {}
		n = len(s)
		for x in range(n):
			if s[x] in d:
				c = max(c, x - d[s[x]] - 1)
			else:
				d[s[x]] = x
		return c


class Solution:

	def maxChars(self, s):
		dict = {}
		dictins = {}
		for i in range(len(s)):
			if s[i] not in dictins:
				dictins[s[i]] = i
		for i in range(len(s)):
			if s[i] in dict:
				tmp = i - dictins[s[i]]
				if tmp > dict[s[i]]:
					dict[s[i]] = tmp
			else:
				dict[s[i]] = i * -1
		maxi = 0
		for i in dict:
			if dict[i] > maxi:
				maxi = dict[i]
		return maxi - 1


class Solution:

	def maxChars(self, s):
		count = -1
		for i in range(len(s)):
			val = s.rfind(s[i])
			if val != s[i]:
				count = max(count, val - i - 1)
		return count


from collections import defaultdict

class Solution:

	def maxChars(self, s):
		d = defaultdict(lambda : [])
		for i in range(0, len(s)):
			d[s[i]].append(i)
		m = -1
		for i in d:
			if len(d[i]) > 1:
				t = d[i]
				m = max(t[len(t) - 1] - t[0] - 1, m)
		return m


class Solution:

	def maxChars(self, s):
		gg = {}
		maxi = -1
		for i in range(len(s)):
			val = s[i]
			if val in gg:
				gg[val].append(i)
			else:
				gg[val] = [i]
		for i in gg:
			if len(gg[i]) >= 2:
				k = gg[i][-1] - gg[i][0] - 1
				maxi = max(maxi, k)
		return maxi


class Solution:

	def maxChars(self, s):
		li = []
		for i in range(125):
			li.append([0, 0])
		for i in range(len(s)):
			if li[ord(s[i])][0] == 0:
				li[ord(s[i])][0] = i + 1
			else:
				li[ord(s[i])][1] = i
		max = 0
		ha = 0
		for i in li:
			if i[0] != 0 and i[1] != 0:
				if abs(i[0] - i[1]) >= max:
					ha = 1
					max = abs(i[0] - i[1])
		if max == 0 and ha == 0:
			return -1
		else:
			return max


class Solution:

	def maxChars(self, s):
		max = -1
		for i in range(len(s)):
			index = s.rfind(s[i])
			m = index - i
			if max < m:
				max = m
		return max - 1


class Solution:

	def maxChars(self, s):
		d = {}
		n = len(s)
		s = list(s)
		if n == len(set(s)):
			return -1
		visited = [0] * 257
		res = 0
		for i in range(n):
			visited[ord(s[i])] = i
		for i in range(n):
			if visited[ord(s[i])] - i > res:
				res = visited[ord(s[i])] - i - 1
		return res


class Solution:

	def maxChars(self, s):
		mymap = {}
		ans = -1
		for e in range(len(s)):
			if s[e] not in mymap:
				mymap[s[e]] = e
			else:
				k = mymap[s[e]]
				if e - k > ans:
					ans = e - k - 1
		return ans


class Solution:

	def maxChars(self, s):
		d = {}
		for i in range(len(s)):
			if s[i] in d:
				d[s[i]].append(i)
			else:
				d[s[i]] = [i]
		score = -1
		for i in d.values():
			if i[-1] - i[0] - 1 > score:
				score = i[-1] - i[0] - 1
		return score