Given a string S consisting of the characters 0, 1 and 2. Your task is to find the length of the smallest substring of string S that contains all the three characters 0, 1 and 2. If no such substring exists, then return -1.
Example 1:
Input:
S = "01212"
Output:
3
Explanation:
The substring 012 is the smallest substring
that contains the characters 0, 1 and 2.
Example 2:
Input: 
S = "12121"
Output:
-1
Explanation: 
As the character 0 is not present in the
string S, therefor no substring containing
all the three characters 0, 1 and 2
exists. Hence, the answer is -1 in this case.
Your Task:
Complete the function smallestSubstring() which takes the string S as input, and returns the length of the smallest substring of string S that contains all the three characters 0, 1 and 2.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}
All the characters of String S lies in the set {'0', '1', '2'}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def smallestSubstring(self, S):

        # Code here

Solutions:
class Solution:

	def smallestSubstring(self, S):
		c = 99999
		x = 0
		y = 0
		o = 0
		z = 0
		t = 0
		for i in range(len(S)):
			if S[i] == '0':
				z += 1
			if S[i] == '1':
				o += 1
			if S[i] == '2':
				t += 1
			y += 1
			while o > 0 and z > 0 and (t > 0):
				if S[x] == '0':
					z -= 1
				if S[x] == '1':
					o -= 1
				if S[x] == '2':
					t -= 1
				if c > y - x:
					c = y - x
				x += 1
		if c != 99999:
			return c
		else:
			return -1


class Solution:

	def smallestSubstring(self, s):
		(zero, one, two) = (-1, -1, -1)
		ans = len(s) + 1
		for i in range(len(s)):
			if s[i] == '0':
				zero = i
			elif s[i] == '1':
				one = i
			else:
				two = i
			if zero != -1 and one != -1 and (two != -1):
				maxi = max(one, two, zero)
				mini = min(one, two, zero)
				ans = min(ans, maxi - mini + 1)
		if ans > len(s):
			return -1
		return ans


class Solution:

	def smallestSubstring(self, S):
		(i, j) = (0, 0)
		m = float('inf')
		d = {}
		while j < len(S):
			if S[j] in d:
				d[S[j]] += 1
			else:
				d[S[j]] = 1
			if len(d) < 3:
				j += 1
			else:
				while len(d) == 3:
					m = min(m, j - i + 1)
					d[S[i]] -= 1
					if d[S[i]] == 0:
						del d[S[i]]
					i += 1
				j += 1
		if m == float('inf'):
			return -1
		return m


import numpy as np

class Solution:

	def smallestSubstring(self, S):
		l = [-1, -1, -1]
		m = np.inf
		for i in range(len(S)):
			l[int(S[i])] = i
			if -1 not in l:
				f = max(l) - min(l) + 1
				if m > f:
					m = f
		if -1 in l:
			return -1
		return m


import sys

class Solution:

	def smallestSubstring(self, S):
		S = list(S)
		zero = -1
		two = -1
		one = -1
		ans = sys.maxsize
		maxi = 0
		mini = sys.maxsize
		for i in range(len(S)):
			if S[i] == '0':
				zero = i
			elif S[i] == '1':
				one = i
			elif S[i] == '2':
				two = i
			if zero != -1 and one != -1 and (two != -1):
				mini = min(zero, min(one, two))
				maxi = max(zero, max(one, two))
				ans = min(ans, maxi - mini + 1)
		if ans != sys.maxsize:
			return ans
		return -1


class Solution:

	def smallestSubstring(self, S):
		n = len(S)
		freq = [0, 0, 0]
		left = right = 0
		min_len = float('inf')
		while right < n:
			freq[int(S[right])] += 1
			while all(freq):
				min_len = min(min_len, right - left + 1)
				freq[int(S[left])] -= 1
				left += 1
			right += 1
		return min_len if min_len != float('inf') else -1


def valid(flg):
	if flg[0] > 0 and flg[1] > 0 and (flg[2] > 0):
		return True
	return False

class Solution:

	def smallestSubstring(self, S):
		flg = [0, 0, 0]
		(fp, sp) = (0, 0)
		ans = len(S) + 1
		while sp < len(S):
			flg[int(S[sp])] += 1
			while valid(flg):
				ans = min(ans, sp - fp + 1)
				flg[int(S[fp])] -= 1
				fp += 1
			sp += 1
		if ans == len(S) + 1:
			return -1
		return ans


import math

class Solution:

	def smallestSubstring(self, s):
		mini = math.inf
		k = 3
		dicti = {}
		n = len(s)
		(i, j) = (0, 0)
		while j < n:
			if s[j] not in dicti:
				dicti[s[j]] = 1
			else:
				dicti[s[j]] += 1
			if len(dicti) < k:
				j += 1
			elif len(dicti) == k:
				mini = min(mini, j - i + 1)
				while len(dicti) == k and i < n:
					dicti[s[i]] -= 1
					if dicti[s[i]] == 0:
						del dicti[s[i]]
					i += 1
					if len(dicti) == k:
						mini = min(mini, j - i + 1)
				j += 1
		if mini != math.inf:
			return mini
		return -1


class Solution:

	def smallestSubstring(self, S):
		arr = [-1, -1, -1]
		res = len(S)
		for i in range(len(S)):
			arr[int(S[i])] = i
			start = min(arr)
			end = max(arr)
			if start != -1:
				res = min(res, end - start + 1)
		if start == -1:
			return -1
		return res


import sys

class Solution:

	def smallestSubstring(self, S):
		zero = False
		one = False
		two = False
		(ans, zeroi, onei, twoi) = (sys.maxsize, 0, 0, 0)
		for i in range(len(S)):
			if S[i] == '0':
				zero = True
				zeroi = i
			if S[i] == '1':
				one = True
				onei = i
			if S[i] == '2':
				two = True
				twoi = i
			if zero and one and two:
				ans = min(ans, max(zeroi, onei, twoi) - min(zeroi, onei, twoi))
		if ans == sys.maxsize:
			return -1
		else:
			return ans + 1


class Solution:

	def smallestSubstring(self, S):
		anslist = False
		ans = len(S)
		(z, on, t) = (-1, -1, -1)
		for i in range(len(S)):
			if S[i] == '0':
				z = i
			elif S[i] == '1':
				on = i
			else:
				t = i
			if z != -1 and on != -1 and (t != -1):
				anslist = True
				ans = min(ans, i + 1 - min(z, on, t))
		if anslist:
			return ans
		return -1


class Solution:

	def smallestSubstring(self, str):
		maxi = 1000000000.0
		strlen = -1
		i = 0
		j = 0
		m = {}
		while i < len(str):
			m[str[i]] = 1 + m.get(str[i], 0)
			if len(m) >= 3:
				while m[str[j]] > 1:
					m[str[j]] -= 1
					j += 1
				maxi = min(maxi, i - j + 1)
			i += 1
		if maxi < 1000000000.0:
			return maxi
		else:
			return -1


class Solution:

	def smallestSubstring(self, S):
		i = 0
		j = 0
		d = {}
		m = 9999999999999
		x = m
		while j < len(S):
			if S[j] in d:
				d[S[j]] += 1
			else:
				d[S[j]] = 1
			if len(d) < 3:
				j += 1
			else:
				while len(d) == 3:
					m = min(m, j - i + 1)
					d[S[i]] -= 1
					if d[S[i]] == 0:
						del d[S[i]]
					i += 1
				j += 1
		if m == x:
			return -1
		return m


class Solution:

	def smallestSubstring(self, s):
		S = list(s)
		n = len(S)
		map = {'0': 0, '1': 1, '2': 2}
		for i in range(n):
			S[i] = map[S[i]]
		map = {0: -1, 1: -1, 2: -1}
		flag = {0: False, 1: False, 2: False}
		(i, j, res) = (0, 0, n)
		while j < n:
			(map[S[j]], flag[S[j]]) = (j, True)
			while i < n and map[S[i]] != i:
				i += 1
			if flag == {0: True, 1: True, 2: True}:
				res = min(res, j - i + 1)
			j += 1
		if res < 3 or flag != {0: True, 1: True, 2: True}:
			return -1
		return res


class Solution:

	def smallestSubstring(self, S):
		res = 99999999999999
		z = 0
		o = 0
		t = 0
		zIndex = 0
		oIndex = 0
		tIndex = 0
		for i in range(len(S)):
			if S[i] == '0':
				z = 1
				zIndex = i
			elif S[i] == '1':
				oIndex = i
				o = 1
			elif S[i] == '2':
				tIndex = i
				t = 1
			if z and o and t:
				res = min(res, max({zIndex, oIndex, tIndex}) - min({zIndex, oIndex, tIndex}))
		if res == 99999999999999:
			return -1
		else:
			return res + 1


class Solution:

	def smallestSubstring(self, S):
		flag = False
		newDict = {}
		minWind = len(S)
		for i in range(len(S)):
			newDict[S[i]] = i
			if len(newDict) == 3:
				newArr = []
				for i in range(3):
					newArr.append(newDict[str(i)])
				minWind = min(minWind, max(newArr) - min(newArr) + 1)
		return -1 if len(newDict) != 3 else minWind


class Solution:

	def smallestSubstring(self, S):
		(id0, id1, id2) = (-1, -1, -1)
		minWind = len(S)
		for i in range(len(S)):
			if S[i] == '0':
				id0 = i
			elif S[i] == '1':
				id1 = i
			else:
				id2 = i
			idL = (id0, id1, id2)
			if -1 not in idL:
				minWind = min(minWind, max(idL) - min(idL) + 1)
		if -1 in idL:
			return -1
		return minWind


class Solution:

	def smallestSubstring(self, S):
		d = {}
		min1 = len(S)
		count = 0
		j = 0
		s = S
		if len(set(S)) < 3:
			return -1
		for i in range(len(S)):
			if s[i] in d:
				d[s[i]] += 1
			else:
				d[s[i]] = 1
			if d[s[i]] == 1:
				count += 1
				while count == 3:
					if min1 > i - j + 1:
						min1 = i - j + 1
					d[s[j]] -= 1
					if d[s[j]] == 0:
						count -= 1
					j += 1
		return min1


class Solution:

	def smallestSubstring(self, S):
		answerExist = False
		(lastZero, lastOne, lastTwo) = (-1, -1, -1)
		ans = len(S)
		for i in range(len(S)):
			if S[i] == '0':
				lastZero = i
			elif S[i] == '1':
				lastOne = i
			else:
				lastTwo = i
			if lastZero != -1 and lastOne != -1 and (lastTwo != -1):
				answerExist = True
				ans = min(ans, 1 + i - min(lastZero, min(lastOne, lastTwo)))
		if answerExist:
			return ans
		return -1


class Solution:

	def smallestSubstring(self, S):
		(zero, zeroi) = (False, -1)
		(one, onei) = (False, -1)
		(two, twoi) = (False, -1)
		ans = float('inf')
		for (idx, ch) in enumerate(S):
			if ch == '0':
				zero = True
				zeroi = idx
			elif ch == '1':
				one = True
				onei = idx
			elif ch == '2':
				two = True
				twoi = idx
			if zero and two and one:
				ans = min(ans, max(zeroi, onei, twoi) - min(zeroi, onei, twoi))
		if ans == float('inf'):
			return -1
		else:
			return ans + 1


class Solution:

	def smallestSubstring(self, S):
		d = {}
		left = 0
		current = 0
		have = 0
		want = 3
		ans = -1
		for i in range(len(S)):
			d[S[i]] = 1 + d.get(S[i], 0)
			if d[S[i]] == 1:
				have += 1
			while have == want and i > left:
				if ans == -1:
					ans = i + 1 - left
				else:
					ans = min(ans, i + 1 - left)
				d[S[left]] -= 1
				if d[S[left]] == 0:
					have -= 1
				left += 1
		return ans


class Solution:

	def smallestSubstring(self, arr):
		m = 9999999999
		a = 0
		b = 0
		c = 0
		a1 = -1
		b1 = -1
		c1 = -1
		for i in range(len(arr)):
			if arr[i] == '0':
				a = 1
				ai = i
			elif arr[i] == '1':
				b = 1
				bi = i
			else:
				c = 1
				ci = i
			if a and b and c:
				m = min(m, max(ai, bi, ci) - min(ai, bi, ci))
		if m == 9999999999:
			return -1
		return m + 1


from collections import Counter

class Solution:

	def smallestSubstring(self, S):
		mini = float('inf')
		n = len(S)
		i = 0
		j = 3
		c = Counter(S[i:j])
		while i < n:
			while j < n and len(c) < 3:
				c[S[j]] += 1
				j += 1
			if len(c) == 3:
				mini = min(mini, j - i)
			c[S[i]] -= 1
			if c[S[i]] == 0:
				del c[S[i]]
			i += 1
		return mini if mini <= n else -1


class Solution:

	def smallestSubstring(self, S):
		i = 0
		j = 0
		mini = len(S)
		d = {}
		res = -1
		while j < len(S):
			if S[j] in d:
				d[S[j]] += 1
			else:
				d[S[j]] = 1
			while len(d) == 3:
				mini = min(mini, j - i + 1)
				d[S[i]] = d[S[i]] - 1
				if d[S[i]] == 0:
					del d[S[i]]
				i = i + 1
			j = j + 1
		if '0' not in S or '1' not in S or '2' not in S:
			return res
		return mini


class Solution:

	def smallestSubstring(self, s):
		c = [-1, -1, -1]
		ans = 1 << 31
		for i in range(len(s)):
			x = int(s[i])
			c[x] = i
			if -1 not in c:
				ans = min(ans, max(c) - min(c) + 1)
		if ans == 1 << 31:
			return -1
		return ans


class Solution:

	def smallestSubstring(self, s):
		d = {}
		d['0'] = -1
		d['1'] = -1
		d['2'] = -1
		ans = 1000000
		for i in range(len(s)):
			d[s[i]] = i
			if d['0'] != -1 and d['1'] != -1 and (d['2'] != -1):
				ans = min(ans, max(d['0'], d['1'], d['2']) - min(d['0'], d['1'], d['2']))
		if ans == 1000000:
			return -1
		else:
			return ans + 1


class Solution:

	def smallestSubstring(self, S):
		count = [0, 0, 0]
		l = r = 0
		count[int(S[l])] = 1
		mi = 100000000000
		while l < len(S) and r < len(S):
			if count[0] != 0 and count[1] != 0 and (count[2] != 0):
				mi = min(mi, r - l + 1)
			if count[int(S[l])] > 1:
				count[int(S[l])] -= 1
				l += 1
			else:
				r += 1
				if r < len(S):
					count[int(S[r])] += 1
		if mi == 100000000000:
			return -1
		else:
			return mi


import collections

class Solution:

	def smallestSubstring(self, s):
		mp = {'0': 1, '1': 1, '2': 1}
		n = len(s)
		m = collections.defaultdict(int)
		count = 0
		j = 0
		res = float('inf')
		for i in range(n):
			a = s[i]
			if a in mp:
				m[a] += 1
				if mp[a] >= m[a]:
					count += 1
			if count == 3:
				res = min(res, i - j + 1)
				while count == 3:
					b = s[j]
					if b in mp:
						m[b] -= 1
						if m[b] < mp[b]:
							count -= 1
					j += 1
					if count == 3:
						res = min(res, i - j + 1)
			if res == 3:
				return 3
		if res != float('inf'):
			return res
		return -1


class Solution:

	def smallestSubstring(self, arr):
		res = 9999999
		a = 0
		b = 0
		c = 0
		for i in range(len(arr)):
			if arr[i] == '0':
				a = 1
				ai = i
			elif arr[i] == '1':
				b = 1
				bi = i
			else:
				c = 1
				ci = i
			if a and b and c:
				res = min(res, max([ai, bi, ci]) - min([ai, bi, ci]))
		if res == 9999999:
			return -1
		return res + 1


import sys

class Solution:

	def smallestSubstring(self, a):
		mydict = {}
		maxlen = sys.maxsize
		start = 0
		end = 0
		n = len(a)
		while end < n:
			while len(mydict) != 3:
				if end >= n:
					break
				if a[end] not in mydict:
					mydict[a[end]] = 1
				else:
					mydict[a[end]] += 1
				end += 1
			while len(mydict) == 3:
				if a[start] in mydict:
					mydict[a[start]] -= 1
				if mydict[a[start]] == 0:
					del mydict[a[start]]
				maxlen = min(maxlen, end - start)
				start += 1
		if maxlen == sys.maxsize:
			return -1
		return maxlen


class Solution:

	def smallestSubstring(self, s):
		dic = {}
		mini = 10000000000
		i = 0
		for j in range(len(s)):
			dic[s[j]] = 1 + dic.get(s[j], 0)
			while len(dic) == 3:
				mini = min(mini, j - i + 1)
				dic[s[i]] -= 1
				if dic[s[i]] == 0:
					dic.pop(s[i])
				i += 1
		if mini == 10000000000:
			return -1
		return mini


class Solution:

	def smallestSubstring(self, S):
		x = '012'
		dict = {}
		for i in range(len(x)):
			if x[i] not in dict:
				dict[x[i]] = 1
			else:
				dict[x[i]] += 1
		dict_size = 3
		startpointer = 0
		endpointer = 0
		min_value = 9999999999999999999999999999999999999999999999999999999999999999999999999999
		while endpointer < len(S):
			if S[endpointer] in dict:
				dict[S[endpointer]] -= 1
				if dict[S[endpointer]] == 0:
					dict_size -= 1
			while dict_size == 0:
				if S[startpointer] in dict:
					dict[S[startpointer]] += 1
					if dict[S[startpointer]] > 0:
						dict_size += 1
				if endpointer - startpointer < min_value:
					min_value = endpointer - startpointer
				startpointer += 1
			endpointer += 1
		if min_value == 9999999999999999999999999999999999999999999999999999999999999999999999999999:
			return -1
		else:
			return min_value + 1


class Solution:

	def smallestSubstring(self, S):
		(zero, one, two) = (False, False, False)
		res = float('inf')
		(zeroi, onei, twoi) = (0, 0, 0)
		for i in range(len(S)):
			if S[i] == '0':
				zero = True
				zeroi = i
			if S[i] == '1':
				one = True
				onei = i
			if S[i] == '2':
				two = True
				twoi = i
			if zero and one and two:
				res = min(res, max(zeroi, onei, twoi) - min(zeroi, onei, twoi))
		if res == float('inf'):
			return -1
		else:
			return res + 1


class Solution:

	def smallestSubstring(self, S):
		count = 3
		mp = {}
		for k in range(3):
			mp[k] = 1
		i = 0
		j = 0
		n = len(S)
		min_len = 9999999
		while j < n:
			if int(S[j]) in mp:
				mp[int(S[j])] -= 1
				if mp[int(S[j])] == 0:
					count -= 1
			if count == 0:
				min_len = min(min_len, j - i + 1)
				while count == 0:
					if int(S[i]) in mp:
						if mp[int(S[i])] < 0:
							mp[int(S[i])] += 1
							i += 1
							min_len = min(min_len, j - i + 1)
						else:
							mp[int(S[i])] += 1
							i += 1
							count += 1
					else:
						i += 1
						min_len = min(min_len, j - i + 1)
			j += 1
		if min_len == 9999999:
			return -1
		return min_len


class Solution:

	def smallestSubstring(self, S):
		res = 999999
		zero = 0
		one = 0
		two = 0
		zeroindex = 0
		oneindex = 0
		twoindex = 0
		for i in range(len(S)):
			if S[i] == '0':
				zero = 1
				zeroindex = i
			elif S[i] == '1':
				one = 1
				oneindex = i
			elif S[i] == '2':
				two = 1
				twoindex = i
			if zero and one and two:
				res = min(res, max([zeroindex, oneindex, twoindex]) - min([zeroindex, oneindex, twoindex]))
		if res == 999999:
			return -1
		return res + 1


class Solution:

	def smallestSubstring(self, s):
		d = {'0': 0, '1': 0, '2': 0}
		i = 0
		j = 0
		ans = float('inf')
		while i < len(s):
			d[s[i]] += 1
			if d['0'] >= 1 and d['1'] >= 1 and (d['2'] >= 1):
				while d[s[j]] > 1:
					d[s[j]] -= 1
					j += 1
				ans = min(ans, i - j + 1)
			i += 1
		return ans if ans != float('inf') else -1


class Solution:

	def smallestSubstring(self, S):
		m = set(S)
		if '0' not in m or '1' not in m or '2' not in m:
			return -1
		else:
			ans = len(S)
			ma = {}
			(i, j) = (0, 0)
			while j < len(S):
				ma[S[j]] = ma.get(S[j], 0) + 1
				if len(ma) < 3:
					j += 1
				elif len(ma) == 3:
					ans = min(ans, j - i + 1)
					while len(ma) == 3:
						ma[S[i]] -= 1
						if ma[S[i]] == 0:
							del ma[S[i]]
						ans = min(ans, j - i + 1)
						i += 1
					j += 1
			return ans


class Solution:

	def smallestSubstring(self, S):
		n = len(S)
		z = -1
		o = -1
		t = -1
		ans = 10 ** 9
		for i in range(n):
			if S[i] == '0':
				z = i
			if S[i] == '1':
				o = i
			if S[i] == '2':
				t = i
			if z != -1 and o != -1 and (t != -1):
				ans = min(ans, max([z, o, t]) - min([z, o, t]))
		if ans == 10 ** 9:
			return -1
		else:
			return ans + 1


from collections import defaultdict

class Solution:

	def smallestSubstring(self, S):
		dict1 = defaultdict(lambda : 0)
		i = 0
		j = 0
		count = 0
		ans = 99999999
		while j < len(S):
			dict1[S[j]] += 1
			if len(dict1) == 3:
				while len(dict1) == 3:
					ans = min(ans, j - i + 1)
					dict1[S[i]] -= 1
					if dict1[S[i]] == 0:
						del dict1[S[i]]
					i += 1
			j += 1
		if ans == 99999999:
			return -1
		return ans


class Solution:

	def smallestSubstring(self, S):
		res = 99999
		zero = 0
		first = 0
		second = 0
		zeroIndex = 0
		firstIndex = 0
		secondIndex = 0
		for i in range(len(S)):
			if S[i] == '0':
				zero = 1
				zeroIndex = i
			elif S[i] == '1':
				first = 1
				firstIndex = i
			else:
				second = 2
				secondIndex = i
			if zero and first and second:
				res = min(res, max([zeroIndex, firstIndex, secondIndex]) - min([zeroIndex, firstIndex, secondIndex]))
		if res == 99999:
			return -1
		else:
			return res + 1


class Solution:

	def smallestSubstring(self, S):
		arr = [-1, -1, -1]
		minn = len(S)
		for i in range(len(S)):
			arr[int(S[i])] = i
			strt = min(arr)
			end = max(arr)
			if strt != -1:
				minn = min(minn, end - strt + 1)
		if strt == -1:
			return -1
		return minn


class Solution:

	def smallestSubstring(self, s):
		m = {}
		for i in s:
			m[i] = 1
		j = 0
		i = 0
		m = {}
		n = len(s)
		d = 9999999999
		while j < n:
			if s[j] in m:
				m[s[j]] += 1
			else:
				m[s[j]] = 1
			if len(m) == 3:
				while True:
					m[s[i]] -= 1
					if m[s[i]] == 0:
						p = i
						g = s[i]
						i += 1
						break
					i += 1
				del m[g]
				if j - p + 1 < d:
					d = j - p + 1
			j += 1
		if d == 9999999999:
			return -1
		return d


class Solution:

	def smallestSubstring(self, s):
		dct = {}
		start = 0
		i = 0
		mini = 1000001
		fg = 0
		while i < len(s):
			dct[s[i]] = dct.get(s[i], 0) + 1
			if len(dct) == 3:
				while len(dct) == 3:
					fg = 1
					if dct[s[start]] > 1:
						dct[s[start]] -= 1
						start += 1
					else:
						break
				mini = min(mini, i - start + 1)
				if mini == 3:
					return 3
			i += 1
		if fg:
			return mini
		return -1


class Solution:

	def smallestSubstring(self, S):
		(zero, one, two) = (False, False, False)
		n = len(S)
		(start, end, mid) = (0, 0, 0)
		min_len = n + 1
		for i in range(n):
			if S[i] == '0':
				zero = True
				start = i
			elif S[i] == '1':
				one = True
				mid = i
			elif S[i] == '2':
				two = True
				end = i
			if one and two and zero:
				a = max(start, mid)
				a = max(a, end)
				b = min(start, mid)
				b = min(b, end)
				min_len = min(min_len, a - b + 1)
		if not one or not two or (not zero):
			return -1
		return min_len


class Solution:

	def smallestSubstring(self, S):
		i = j = 0
		n = len(S)
		z = o = t = 0
		ans = 10 ** 9
		p = q = r = 0
		for x in S:
			if x == '0':
				p += 1
			elif x == '1':
				q += 1
			else:
				r += 1
		if p == 0 or r == 0 or q == 0:
			return -1
		while j < n:
			if S[j] == '0':
				z += 1
			elif S[j] == '1':
				o += 1
			else:
				t += 1
			if z >= 1 and o >= 1 and (t >= 1):
				while z != 0 and o != 0 and (t != 0):
					ans = min(ans, j - i + 1)
					if S[i] == '0':
						z -= 1
					elif S[i] == '1':
						o -= 1
					else:
						t -= 1
					i += 1
			j += 1
		while z != 0 and o != 0 and (t != 0):
			ans = min(ans, j - i)
			if S[i] == '0':
				z -= 1
			elif S[i] == '1':
				o -= 1
			else:
				t -= 1
			i += 1
		return ans


from collections import defaultdict

class Solution:

	def smallestSubstring(self, s):
		hmap = defaultdict(int)
		total = 0
		j = -1
		ans = float('inf')
		for i in range(len(s)):
			hmap[s[i]] += 1
			if hmap[s[i]] == 1:
				total += 1
			while total == 3:
				ans = min(ans, i - j)
				j += 1
				hmap[s[j]] -= 1
				if hmap[s[j]] == 0:
					total -= 1
		return ans if ans <= len(s) else -1


class Solution:

	def smallestSubstring(self, S):
		if '1' not in S or '0' not in S or '2' not in S:
			return -1
		zero = one = two = len(S)
		length = float('inf')
		for (i, v) in enumerate(S):
			if v == '0':
				zero = i
			elif v == '1':
				one = i
			else:
				two = i
			length = min(length, max(one, two, zero) - min(one, two, zero) + 1)
		return length
		return count


class Solution:

	def smallestSubstring(self, S):
		zero = False
		one = False
		two = False
		zi = 0
		oi = 0
		ti = 0
		lenn = 999999
		for i in range(len(S)):
			if S[i] == '0':
				zero = True
				zi = i
			elif S[i] == '1':
				one = True
				oi = i
			else:
				two = True
				ti = i
			if zero and one and two:
				lenn = min(lenn, max(oi, zi, ti) - min(oi, zi, ti) + 1)
		if lenn == 999999:
			return -1
		return lenn


class Solution:

	def smallestSubstring(self, s):
		z = False
		o = False
		t = False
		(zi, oi, ti) = (0, 0, 0)
		lenn = 99999999
		for i in range(len(s)):
			if s[i] == '0':
				z = True
				zi = i
			elif s[i] == '1':
				o = True
				oi = i
			else:
				t = True
				ti = i
			if z and o and t:
				lenn = min(lenn, max(zi, oi, ti) - min(zi, oi, ti) + 1)
		if lenn == 99999999:
			return -1
		return lenn


class Solution:

	def smallestSubstring(self, s):
		one = False
		two = False
		zero = False
		(z, o, t) = (0, 0, 0)
		lenn = 99999999
		for i in range(len(s)):
			if s[i] == '0':
				zero = True
				z = i
			elif s[i] == '1':
				one = True
				o = i
			else:
				two = True
				t = i
			if zero and one and two:
				lenn = min(lenn, max(z, o, t) - min(z, o, t) + 1)
		if lenn == 99999999:
			return -1
		return lenn


class Solution:

	def smallestSubstring(self, S):
		zero = False
		one = False
		two = False
		(zi, oi, ti) = (0, 0, 0)
		le = len(S) + 2
		for i in range(len(S)):
			if S[i] == '0':
				zero = True
				zi = i
			if S[i] == '1':
				one = True
				oi = i
			if S[i] == '2':
				two = True
				ti = i
			if zero and one and two:
				le = min(le, max(zi, oi, ti) - min(zi, oi, ti) + 1)
		if le == len(S) + 2:
			return -1
		return le


class Solution:

	def smallestSubstring(self, s):
		a = [-1, -1, -1]
		r = len(s)
		for i in range(len(s)):
			a[int(s[i])] = i
			start = min(a)
			end = max(a)
			if start != -1:
				r = min(r, end - start + 1)
		if start == -1:
			return -1
		return r


import math

class Solution:

	def smallestSubstring(self, S):
		Hashmap = {'0': math.inf, '1': math.inf, '2': math.inf}
		(s, e) = (0, 0)
		n = len(S)
		smallestStr = math.inf
		while e < n:
			Hashmap[S[e]] = e
			s = min(Hashmap.values())
			e += 1
			if math.inf not in Hashmap.values():
				smallestStr = min(smallestStr, e - s)
		if smallestStr == math.inf:
			return -1
		else:
			return smallestStr
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


class Solution:

	def smallestSubstring(self, S):
		arr = [-1, -1, -1]
		res = len(S)
		for i in range(len(S)):
			arr[int(S[i])] = i
			start = min(arr)
			end = max(arr)
			if start != -1:
				res = min(res, end - start + 1)
		if start == -1:
			return -1
		return res
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


class Solution:

	def smallestSubstring(self, S):
		ans = float('inf')
		(zero, one, two) = (0, 0, 0)
		(zeroIndex, oneIndex, twoIndex) = (0, 0, 0)
		for i in range(len(S)):
			if S[i] == '0':
				zero = 1
				zeroIndex = i
			elif S[i] == '1':
				one = 1
				oneIndex = i
			elif S[i] == '2':
				two = 2
				twoIndex = i
			if zero and one and two:
				ans = min(ans, max([zeroIndex, oneIndex, twoIndex]) - min([zeroIndex, oneIndex, twoIndex]))
		if ans == float('inf'):
			return -1
		else:
			return ans + 1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


class Solution:

	def smallestSubstring(self, S):
		i = 0
		j = 0
		a = {}
		maxi = float('inf')
		while j < len(S):
			if S[j] not in a:
				a[S[j]] = 1
			else:
				a[S[j]] = a[S[j]] + 1
			if len(a) < 3:
				j = j + 1
			elif len(a) == 3:
				while len(a) == 3:
					maxi = min(maxi, j - i + 1)
					a[S[i]] = a[S[i]] - 1
					if a[S[i]] == 0:
						del a[S[i]]
					i = i + 1
				j = j + 1
		if maxi == float('inf'):
			return -1
		return maxi
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


import sys

class Solution:

	def smallestSubstring(self, S):
		minLen = sys.maxsize
		temp1 = temp2 = temp3 = check = False
		zero = one = two = -1
		for i in range(len(S)):
			if S[i] == '0':
				temp1 = True
				zero = i
			if S[i] == '1':
				temp2 = True
				one = i
			if S[i] == '2':
				temp3 = True
				two = i
			if temp1 == True and temp2 == True and (temp3 == True):
				check = True
				window = max(zero, one, two) - min(zero, one, two) + 1
				minLen = min(minLen, window)
		if check == False:
			return -1
		else:
			return minLen
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


class Solution:

	def smallestSubstring(self, S):
		d = {}
		min1 = len(S)
		count = 0
		j = 0
		s = S
		if len(set(S)) < 3:
			return -1
		for i in range(len(S)):
			if s[i] in d:
				d[s[i]] += 1
			else:
				d[s[i]] = 1
			if d[s[i]] == 1:
				count += 1
				while count == 3:
					if min1 > i - j + 1:
						min1 = i - j + 1
					d[s[j]] -= 1
					if d[s[j]] == 0:
						count -= 1
					j += 1
		return min1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


class Solution:

	def smallestSubstring(self, S):
		import sys
		zero = False
		one = False
		two = False
		min_window = sys.maxsize
		zeroidx = 0
		oneidx = 0
		twoidx = 0
		for i in range(len(S)):
			if S[i] == '0':
				zero = True
				zeroidx = i
			elif S[i] == '1':
				one = True
				oneidx = i
			elif S[i] == '2':
				two = True
				twoidx = i
			if zero and one and two:
				min_window = min(min_window, max(zeroidx, oneidx, twoidx) - min(zeroidx, oneidx, twoidx) + 1)
		return min_window if zero and one and two else -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


class Solution:

	def smallestSubstring(self, S):
		answerExist = False
		(lastZero, lastOne, lastTwo) = (-1, -1, -1)
		ans = len(S)
		for i in range(len(S)):
			if S[i] == '0':
				lastZero = i
			elif S[i] == '1':
				lastOne = i
			else:
				lastTwo = i
			answerExist = -1 not in (lastZero, lastOne, lastTwo)
			if answerExist:
				ans = min(ans, 1 + i - min(lastZero, min(lastOne, lastTwo)))
		return ans if answerExist else -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


class Solution:

	def smallestSubstring(self, s):
		(d, _min) = ({}, float('inf'))
		i = c = start = 0
		while i < len(s):
			if s[i] not in d or d[s[i]] == 0:
				(d[s[i]], c) = (1, c + 1)
			else:
				d[s[i]] += 1
			while c == 3:
				_min = min(_min, i - start + 1)
				d[s[start]] -= 1
				c -= d[s[start]] == 0
				start += 1
			i += 1
		return (_min, -1)[_min == float('inf')]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)


import re

class Solution:

	def smallestSubstring(self, s):
		x1 = re.findall('[0][1]+[2]', s)
		x2 = re.findall('[0][2]+[1]', s)
		x3 = re.findall('[1][0]+[2]', s)
		x4 = re.findall('[1][2]+[0]', s)
		x5 = re.findall('[2][0]+[1]', s)
		x6 = re.findall('[2][1]+[0]', s)
		a = x1 + x2 + x3 + x4 + x5 + x6
		a = sorted(a, key=len)
		if len(a) == 0:
			return -1
		else:
			return len(a[0])
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		S = input()
		ob = Solution()
		ans = ob.smallestSubstring(S)
		print(ans)