Given a list of words followed by two words, the task to find the minimum distance between the given two words in the list of words
Example 1:
Input:
S = { "the", "quick", "brown", "fox", 
     "quick"}
word1 = "the"
word2 = "fox"
Output: 3
Explanation: Minimum distance between the 
words "the" and "fox" is 3
Example 2:
Input:
S = {"geeks", "for", "geeks", "contribute", 
     "practice"}
word1 = "geeks"
word2 = "practice"
Output: 2
Explanation: Minimum distance between the
words "geeks" and "practice" is 2
Your Task:  
You don't need to read input or print anything. Your task is to complete the function 
shortestDistance() which list of words, two strings as inputs and returns the minimum distance between two words
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
Sum of lengths of words ≤ 10^{5}
Note: word1 and word2 are both in the list.

Difficulty: EASY
Tags: String algorithms

Sorting

Data structures
Skill types: Sorting

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

Starter code:
#User function Template for python3



class Solution:

	def shortestDistance(self, s, word1, word2):

		# code here

Solutions:
class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		d = {}
		res = float('inf')
		for i in range(len(s)):
			if s[i] not in d:
				if word2 == s[i]:
					if word1 in d:
						res = min(res, i - d[word1])
				if word1 == s[i]:
					if word2 in d:
						res = min(res, i - d[word2])
				d[s[i]] = i
			else:
				d[s[i]] = i
				if word2 == s[i]:
					if word1 in d:
						res = min(res, i - d[word1])
				if word1 == s[i]:
					if word2 in d:
						res = min(res, i - d[word2])
		return res


class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		d = {}
		fm = []
		for i in range(len(s)):
			if s[i] not in d:
				if s[i] == word1:
					if word2 in d:
						fm.append(abs(i - d[word2]))
				if s[i] == word2:
					if word1 in d:
						fm.append(abs(i - d[word1]))
				d[s[i]] = i
			else:
				if s[i] == word1:
					if word2 in d:
						fm.append(abs(i - d[word2]))
				if s[i] == word2:
					if word1 in d:
						fm.append(abs(i - d[word1]))
				d[s[i]] = i
		return min(fm)


class Solution:

	def shortestDistance(self, s, word1, word2):
		minm = float('inf')
		s1 = None
		s2 = None
		for i in range(len(s)):
			if s[i] == word1:
				s1 = i
			if s[i] == word2:
				s2 = i
			if s1 != None and s2 != None:
				minm = min(abs(s1 - s2), minm)
		return minm


class Solution:

	def shortestDistance(self, s, word1, word2):
		minm = float('inf')
		pos1 = None
		pos2 = None
		for i in range(len(s)):
			if s[i] == word1:
				pos1 = i
			if s[i] == word2:
				pos2 = i
			if pos1 != None and pos2 != None:
				minm = min(abs(pos1 - pos2), minm)
		return minm


class Solution:

	def shortestDistance(self, s, word1, word2):
		index = -1
		min_dist = float('inf')
		for i in range(len(s)):
			if s[i] == word1 and s[i] == word2:
				return 0
			if s[i] == word1 or s[i] == word2:
				if index != -1 and s[i] != s[index]:
					min_dist = min(min_dist, i - index)
				index = i
		return min_dist


class Solution:

	def shortestDistance(self, s, word1, word2):
		min_distance = float('inf')
		prev_index = -1
		for i in range(len(s)):
			if word1 == word2:
				min_distance = 0
			if s[i] == word1 or s[i] == word2:
				if prev_index != -1 and s[i] != s[prev_index]:
					min_distance = min(min_distance, i - prev_index)
				prev_index = i
		return min_distance


class Solution:

	def shortestDistance(self, s, word1, word2):
		p = list(s)
		k = 99999999
		for i in range(len(p)):
			if p[i] == word1:
				for j in range(i, len(p)):
					if p[j] == word2:
						k = min(k, j - i)
		for i in range(len(p) - 1, -1, -1):
			if p[i] == word1:
				for j in range(i, -1, -1):
					if p[j] == word2:
						k = min(k, i - j)
		if k != 99999999:
			return k


class Solution:

	def shortestDistance(self, s, word1, word2):
		x = 10 ** 9
		y = 10 ** 9
		mini = 10 ** 9
		for i in range(len(s)):
			if s[i] == word1:
				if x != 10 ** 9:
					mini = min(mini, i - x)
				y = i
			elif s[i] == word2:
				if y != 10 ** 9:
					mini = min(mini, i - y)
				x = i
		if mini == 10 ** 9:
			return 0
		return mini


class Solution:

	def shortestDistance(self, s, word1, word2):
		w1_index = []
		w2_index = []
		for (i, word) in enumerate(s):
			if word == word2 and word == word1:
				w1_index.append(i)
				w2_index.append(i)
			elif word == word1:
				w1_index.append(i)
			elif word == word2:
				w2_index.append(i)
		min_dis = 10000000000000000000
		for x in w1_index:
			for y in w2_index:
				res = abs(x - y)
				if res < min_dis:
					min_dis = res
		return min_dis


class Solution:

	def shortestDistance(self, s, a, b):
		if a == b:
			return 0
		d1 = d2 = -1
		ans = len(s)
		for i in range(len(s)):
			if s[i] == a:
				d1 = i
			elif s[i] == b:
				d2 = i
			if d2 > -1 and d1 > -1:
				ans = min(ans, abs(d2 - d1))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		word1_dist = float('inf')
		word2_dist = float('inf')
		min_dist = float('inf')
		for (i, word) in enumerate(s):
			if word == word1:
				word1_dist = i
			if word == word2:
				word2_dist = i
			min_dist = min(min_dist, abs(word1_dist - word2_dist))
		return min_dist


class Solution:

	def shortestDistance(self, s, word1, word2):
		mini = float('inf')
		a = None
		b = None
		for i in range(len(s)):
			if s[i] == word1:
				a = i
			if s[i] == word2:
				b = i
			if a != None and b != None:
				mini = min(abs(a - b), mini)
		return mini


import sys

class Solution:

	def shortestDistance(self, s, word1, word2):
		dis = sys.maxsize
		flag1 = False
		flag2 = False
		for i in range(len(s)):
			if s[i] == word1:
				i1 = i
				flag1 = True
			if s[i] == word2:
				i2 = i
				flag2 = True
			if flag1 and flag2:
				dis = min(dis, abs(i1 - i2))
		return dis


class Solution:

	def shortestDistance(self, s, word1, word2):
		a = []
		b = []
		p = []
		for i in range(len(s)):
			if s[i] == word1:
				a.append(i)
			if s[i] == word2:
				b.append(i)
		for k in range(len(a)):
			for j in range(len(b)):
				f = a[k] - b[j]
				p.append(abs(f))
		return min(p)


class Solution:

	def shortestDistance(self, s, word1, word2):
		first = -1
		second = -1
		result = 999999
		for i in range(0, len(s)):
			if s[i] == word1:
				first = i
			if s[i] == word2:
				second = i
			if first != -1 and second != -1:
				result = min(result, abs(first - second))
		return result


import sys

class Solution:

	def shortestDistance(self, s, word1, word2):
		indi1 = -1
		indi2 = -1
		mini = sys.maxsize
		for i in range(0, len(s)):
			if s[i] == word1:
				indi1 = i
			if s[i] == word2:
				indi2 = i
			if indi1 != -1 and indi2 != -1:
				mini = min(mini, abs(indi1 - indi2))
		return mini


class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		w1i = -1
		w2i = -1
		mini = len(s)
		for i in range(len(s)):
			if s[i] == word1:
				w1i = i
			elif s[i] == word2:
				w2i = i
			if w1i != -1 and w2i != -1:
				mini = min(mini, abs(w1i - w2i))
		return mini


class Solution:

	def shortestDistance(self, s, word1, word2):
		d1 = -1
		d2 = -1
		ans = 100000000
		for i in range(len(s)):
			if s[i] == word1:
				d1 = i
			if s[i] == word2:
				d2 = i
			if d1 != -1 and d2 != -1:
				ans = min(ans, abs(d1 - d2))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		minm = float('inf')
		d1 = None
		d2 = None
		for i in range(len(s)):
			if s[i] == word1:
				d1 = i
			if s[i] == word2:
				d2 = i
			if d1 is not None and d2 is not None:
				minm = min(abs(d1 - d2), minm)
		return minm


class Solution:

	def shortestDistance(self, s, word1, word2):
		x = -1
		y = -1
		mini = float('inf')
		for i in range(len(s)):
			if s[i] == word1:
				x = i
			elif s[i] == word2:
				y = i
			if x != -1 and y != -1:
				mini = min(abs(x - y), mini)
		return mini if mini != float('inf') else 0


class Solution:

	def shortestDistance(self, s, word1, word2):
		(a, b) = (-1, -1)
		res = 2 ** 64
		for i in range(len(s)):
			if word1 == s[i]:
				a = i
			if word2 == s[i]:
				b = i
			if a != -1 and b != -1 and (res > abs(a - b)):
				res = abs(a - b)
		return res


class Solution:

	def shortestDistance(self, s, word1, word2):
		list1 = []
		list2 = []
		for i in range(len(s)):
			if word1 == s[i]:
				list1.append(i)
			if word2 == s[i]:
				list2.append(i)
		res = []
		for i in list1:
			for j in list2:
				res.append(abs(i - j))
		return sorted(res)[0]


class Solution:

	def shortestDistance(self, s, word1, word2):
		ind1 = -1
		ind2 = -1
		res = 99999
		for i in range(len(s)):
			if s[i] == word1:
				ind1 = i
			if s[i] == word2:
				ind2 = i
			if ind1 != -1 and ind2 != -1:
				res = min(res, abs(ind2 - ind1))
		return res


class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		first = -1
		last = -1
		res = 9999999
		for i in range(0, len(s)):
			if s[i] == word1:
				first = i
			elif s[i] == word2:
				last = i
			if (first >= 0 and last >= 0) and abs(last - first) < res:
				res = abs(last - first)
		return res


class Solution:

	def shortestDistance(self, s, word1, word2):
		idx1 = s.index(word1)
		idx2 = s.index(word2)
		mindist = abs(idx1 - idx2)
		for i in range(len(s)):
			if s[i] == word1:
				idx1 = i
			elif s[i] == word2:
				idx2 = i
			temp = abs(idx1 - idx2)
			mindist = min(mindist, temp)
		return mindist


class Solution:

	def shortestDistance(self, s, word1, word2):
		k = 0
		l = 0
		count = 0
		minm = 1000000
		for j in range(len(s)):
			if s[j] == word1:
				k = j
				count += 1
			if s[j] == word2:
				l = j
				count += 1
			if count >= 2:
				p = abs(l - k)
				minm = min(minm, p)
		return minm


class Solution:

	def shortestDistance(self, s, word1, word2):
		data = {}
		for i in range(len(s)):
			if s[i] in data:
				data[s[i]].append(i)
			else:
				data[s[i]] = [i]
		(a, b) = (data[word1], data[word2])
		res = float('inf')
		for i in range(len(a)):
			for j in range(len(b)):
				res = min(res, abs(a[i] - b[j]))
		return res


class Solution:

	def shortestDistance(self, s, word1, word2):
		i1 = float('inf')
		i2 = float('inf')
		res1 = float('inf')
		for i in range(len(s)):
			if s[i] == word1:
				if i2 != float('inf'):
					if abs(i - i2) < res1:
						i1 = i
						res1 = abs(i1 - i2)
				else:
					i1 = i
			if s[i] == word2:
				if i1 != float('inf'):
					if abs(i1 - i) < res1:
						i2 = i
						res1 = abs(i1 - i2)
				else:
					i2 = i
		i1 = float('inf')
		i2 = float('inf')
		res2 = float('inf')
		for i in range(len(s) - 1, -1, -1):
			if s[i] == word1:
				if i2 != float('inf'):
					if abs(i - i2) < res2:
						i1 = i
						res2 = abs(i1 - i2)
				else:
					i1 = i
			if s[i] == word2:
				if i1 != float('inf'):
					if abs(i1 - i) < res2:
						i2 = i
						res2 = abs(i1 - i2)
				else:
					i2 = i
		return min(res1, res2)


class Solution:

	def shortestDistance(self, s, word1, word2):
		pos1 = -1
		pos2 = -1
		min_dist = len(s)
		for i in range(len(s)):
			if s[i] == word1:
				pos1 = i
			if s[i] == word2:
				pos2 = i
			if pos1 != -1 and pos2 != -1:
				dist = abs(pos1 - pos2)
				if dist < min_dist:
					min_dist = dist
		return min_dist


class Solution:

	def shortestDistance(self, s, word1, word2):
		f = -1
		se = -1
		mini = 1000000
		for i in range(len(s)):
			if s[i] == word1:
				f = i
			if s[i] == word2:
				se = i
			if f != -1 and se != -1:
				mini = min(mini, abs(f - se))
		return mini


class Solution:

	def shortestDistance(self, s, word1, word2):
		i1 = -1
		i2 = -1
		minDistance = 100000000
		for i in range(len(s)):
			if s[i] == word1:
				i1 = i
			if s[i] == word2:
				i2 = i
			if i1 != -1 and i2 != -1:
				minDistance = min(minDistance, abs(i1 - i2))
		return minDistance


class Solution:

	def shortestDistance(self, s, word1, word2):
		distance = []
		index1 = None
		index2 = None
		for i in range(len(s)):
			if s[i] == word1:
				index1 = i
			if s[i] == word2:
				index2 = i
			if index1 is not None and index2 is not None:
				distance.append(abs(index1 - index2))
		return min(distance)


from collections import defaultdict

class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		n = len(s)
		w1 = -1
		w2 = -1
		diff = []
		for i in range(n):
			if s[i] == word1:
				w1 = i
				if w2 != -1:
					diff.append(i - w2)
			elif s[i] == word2:
				if w1 != -1:
					diff.append(i - w1)
				w2 = i
			else:
				continue
		return abs(min(diff))


class Solution:

	def shortestDistance(self, s, word1, word2):
		ans = len(s)
		(i, j) = (0, 0)
		(f_w1, f_w2) = (False, False)
		for x in range(len(s)):
			if not f_w1 or not f_w2:
				if s[x] == word1:
					f_w1 = True
					i = x
				if s[x] == word2:
					f_w2 = True
					j = x
			if f_w1 and f_w2:
				ans = min(ans, abs(j - i))
				if s[x] == word1:
					i = x
				if s[x] == word2:
					j = x
				ans = min(ans, abs(j - i))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		idx1 = [i for (i, x) in enumerate(s) if x == word1]
		idx2 = [i for (i, x) in enumerate(s) if x == word2]
		ans = float('inf')
		for a in idx1:
			for b in idx2:
				ans = min(ans, abs(a - b))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		in1 = []
		in2 = []
		final = []
		for i in range(len(s)):
			if word1 == s[i]:
				in1.append(i)
		for m in range(len(s)):
			if word2 == s[m]:
				in2.append(m)
		for j in in2:
			for k in in1:
				final.append(abs(j - k))
		final.sort()
		return final[0]


import sys

class Solution:

	def shortestDistance(self, s, word1, word2):
		ind1 = sys.maxsize
		ind2 = sys.maxsize
		ans = sys.maxsize
		for i in range(len(s)):
			if s[i] == word1:
				ind1 = i
				ans = min(ans, abs(int(ind1) - int(ind2)))
			if s[i] == word2:
				ind2 = i
				ans = min(ans, abs(int(ind1) - int(ind2)))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		dis = float('+inf')
		result = 0
		if word1 == word2:
			return 0
		for i in range(0, len(s)):
			if s[i] == word1 or s[i] == word2:
				if s[i] == word1:
					for j in range(i + 1, len(s)):
						if s[j] == word2:
							result = abs(j - i)
							if result < dis:
								dis = result
				if s[i] == word2:
					for j in range(i + 1, len(s)):
						if s[j] == word1:
							result = abs(j - i)
							if result < dis:
								dis = result
		return dis


class Solution:

	def shortestDistance(self, s, word1, word2):
		min1 = 9999999
		for i in range(len(s)):
			if s[i] == word1:
				for j in range(len(s)):
					if s[j] == word2:
						min1 = min(min1, abs(j - i))
		return min1


class Solution:

	def shortestDistance(self, s, word1, word2):
		r = []
		a = 0
		b = 0
		count = 0
		for i in range(len(s)):
			if word1 == s[i]:
				a = i
				count += 1
			if word2 == s[i]:
				b = i
				count += 1
			if count >= 2:
				r.append(abs(a - b))
		b = min(r)
		return b


class Solution:

	def shortestDistance(self, s, word1, word2):
		i1 = -1
		i2 = -1
		ans = 9999999999
		for i in range(len(s)):
			if s[i] == word1:
				i1 = i
				if i2 != -1:
					ans = min(ans, abs(i2 - i1))
			if s[i] == word2:
				i2 = i
				if i1 != -1:
					ans = min(ans, abs(i2 - i1))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		self.s = s
		self.word1 = word1
		self.word2 = word2
		wordOneFound = False
		wordTwoFound = False
		distanceBetweenWords = 0
		startIndex = 0
		endIndex = len(self.s) - 1
		minDistanceBetweenWords = len(self.s) - 1
		if self.word1 == self.word2:
			return 0
		for i in range(0, len(self.s)):
			if not (wordOneFound or wordTwoFound):
				if self.s[i] == self.word1:
					startIndex = i
					wordOneFound = True
				elif self.s[i] == self.word2:
					startIndex = i
					wordTwoFound = True
			elif wordOneFound == True and wordTwoFound == False:
				if self.s[i] == self.word1:
					startIndex = i
				elif self.s[i] == self.word2:
					endIndex = i
					distanceBetweenWords = endIndex - startIndex
					if distanceBetweenWords < minDistanceBetweenWords:
						minDistanceBetweenWords = distanceBetweenWords
					startIndex = endIndex
					endIndex = len(self.s) - 1
					wordTwoFound = True
					wordOneFound = False
			elif wordOneFound == False and wordTwoFound == True:
				if self.s[i] == self.word2:
					startIndex = i
				elif self.s[i] == self.word1:
					endIndex = i
					distanceBetweenWords = endIndex - startIndex
					if distanceBetweenWords < minDistanceBetweenWords:
						minDistanceBetweenWords = distanceBetweenWords
					startIndex = endIndex
					endIndex = len(self.s) - 1
					wordOneFound = True
					wordTwoFound = False
		return minDistanceBetweenWords


class Solution:

	def shortestDistance(self, s, word1, word2):
		p1 = -1
		p2 = -1
		i = 0
		if word1 == word2:
			return 0
		ans = float('inf')
		while i < len(s):
			if s[i] == word1:
				p1 = i
			elif s[i] == word2:
				p2 = i
			if p1 >= 0 and p2 >= 0:
				ans = min(ans, abs(p2 - p1))
			i += 1
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		one = -1
		two = -1
		ans = 100000000
		for i in range(len(s)):
			if s[i] == word1:
				one = i
				if two != -1:
					ans = min(ans, abs(one - two))
			if s[i] == word2:
				two = i
				if one != -1:
					ans = min(ans, abs(one - two))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		ans = 1000000000.0 + 7
		lastPos = -1
		for i in range(0, len(s)):
			if s[i] == word1 or s[i] == word2:
				if lastPos == -1:
					lastPos = i
				elif s[lastPos] == s[i]:
					lastPos = i
				else:
					ans = min(ans, i - lastPos)
					lastPos = i
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		d1 = -1
		d2 = -1
		dist = 1000000000
		for i in range(len(s)):
			if s[i] == word1:
				d1 = i
			if s[i] == word2:
				d2 = i
			if d1 != -1 and d2 != -1:
				dist = min(dist, abs(d2 - d1))
		return dist


class Solution:

	def shortestDistance(self, s, word1, word2):
		d1 = d2 = 0
		d1t = d2t = False
		if word1 == word2:
			return 0
		min_dis = float('Inf')
		for i in range(len(s)):
			if s[i] == word1:
				d1 = i
				d1t = True
				if d1t and d2t:
					dis = abs(d2 - d1)
					if min_dis > dis:
						min_dis = dis
			elif s[i] == word2:
				d2 = i
				d2t = True
				if d1t and d2t:
					dis = abs(d2 - d1)
					if min_dis > dis:
						min_dis = dis
		return min_dis


class Solution:

	def shortestDistance(self, s, word1, word2):
		indx1 = []
		indx2 = []
		for (i, word) in enumerate(s):
			if word == word1:
				indx1.append(i)
			if word == word2:
				indx2.append(i)
		min_dist = len(s)
		for i in indx1:
			for j in indx2:
				min_dist = min(min_dist, abs(i - j))
		return min_dist


class Solution:

	def shortestDistance(self, s, word1, word2):
		ind1 = []
		ind2 = []
		for i in range(0, len(s)):
			if s[i] == word1:
				ind1.append(i)
			if s[i] == word2:
				ind2.append(i)
		diff = 0
		d = 100000
		for i in range(0, len(ind1)):
			for j in range(0, len(ind2)):
				diff = abs(ind1[i] - ind2[j])
				d = min(d, diff)
		return d


class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		l = 0
		i = 0
		while i < len(s):
			if s[i] == word1:
				l = 1
				break
			elif s[i] == word2:
				l = 2
				break
			i += 1
		min1 = 10 ** 5
		c = 0
		while i < len(s):
			if s[i] == word1:
				if l == 2:
					l = 1
					min1 = min(min1, c)
				c = 0
			elif s[i] == word2:
				if l == 1:
					l = 2
					min1 = min(min1, c)
				c = 0
			else:
				c += 1
			i += 1
		return min1 + 1


import math

class Solution:

	def shortestDistance(self, s, word1, word2):
		dis = []
		(w1, w2) = (0, 0)
		for i in range(len(s)):
			if s[i] == word1:
				w1 = i + 1
				if w2 != 0:
					dis.append(abs(w2 - w1))
			if s[i] == word2:
				w2 = i + 1
				if w1 != 0:
					dis.append(abs(w2 - w1))
		return min(dis)


class Solution:

	def shortestDistance(self, s, word1, word2):
		start = 0
		i = 0
		j = 0
		dict_1 = {word1: [], word2: []}
		lst_1 = []
		for i in range(len(s)):
			if s[i] == word1:
				dict_1[word1].append(i)
			elif s[i] == word2:
				dict_1[word2].append(i)
		for i in range(len(dict_1[word1])):
			for k in range(len(dict_1[word2])):
				lst_1.append(abs(dict_1[word1][i] - dict_1[word2][k]))
		return min(lst_1)


class Solution:

	def shortestDistance(self, s, word1, word2):
		dist1 = -1
		dist2 = -1
		res = 10000000
		for i in range(len(s)):
			if s[i] == word1:
				dist1 = i
			if s[i] == word2:
				dist2 = i
			if dist1 != -1 and dist2 != -1:
				res = min(res, abs(dist2 - dist1))
		return res


class Solution:

	def shortestDistance(self, s, word1, word2):
		idx1 = []
		idx2 = []
		for (i, word) in enumerate(s):
			if word == word1:
				idx1.append(i)
			if word == word2:
				idx2.append(i)
		min_lst = len(s)
		for i in idx1:
			for j in idx2:
				min_lst = min(min_lst, abs(i - j))
		return min_lst


import sys

class Solution:

	def shortestDistance(self, s, word1, word2):
		i1 = -1
		i2 = -1
		short = 10000000
		for i in range(len(s)):
			if s[i] == word1:
				i1 = i
			if s[i] == word2:
				i2 = i
			if i1 != -1 and i2 != -1:
				short = min(abs(i2 - i1), short)
		return short


class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		import sys
		word1_idx = -1
		word2_idx = -1
		diff = sys.maxsize
		for i in range(len(s)):
			if s[i] == word1:
				word1_idx = i
			elif s[i] == word2:
				word2_idx = i
			if word1_idx > -1 and word2_idx > -1:
				diff = min(diff, abs(word1_idx - word2_idx))
		return diff


class Solution:

	def shortestDistance(self, s, word1, word2):
		ind1 = -1
		ind2 = -1
		ans = float('inf')
		for i in range(len(s)):
			if s[i] == word1:
				ind1 = i
			if s[i] == word2:
				ind2 = i
			if ind1 >= 0 and ind2 >= 0:
				ans = min(ans, abs(ind2 - ind1))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		(ind1, ind2) = (-1, -1)
		m = len(s) + 1
		for i in range(len(s)):
			if s[i] == word1 == word2:
				return 0
			if s[i] == word1:
				ind1 = i
				if ind2 != -1 and ind1 != -1:
					m = min(m, abs(ind1 - ind2))
			elif s[i] == word2:
				ind2 = i
				if ind2 != -1 and ind1 != -1:
					m = min(m, abs(ind1 - ind2))
		m = min(m, abs(ind1 - ind2))
		return m


class Solution:

	def shortestDistance(self, s, word1, word2):
		apart = 999999
		first_wordLocation = -1
		second_wordLocation = -1
		for i in range(len(s)):
			if word1 == s[i]:
				first_wordLocation = i
				if (first_wordLocation != -1 and second_wordLocation != -1) and abs(second_wordLocation - first_wordLocation) == 1:
					return 1
				if first_wordLocation != -1 and second_wordLocation != -1:
					apart = min(abs(second_wordLocation - first_wordLocation), apart)
			elif word2 == s[i]:
				second_wordLocation = i
				if (first_wordLocation != -1 and second_wordLocation != -1) and abs(second_wordLocation - first_wordLocation) == 1:
					return 1
				if first_wordLocation != -1 and second_wordLocation != -1:
					apart = min(abs(second_wordLocation - first_wordLocation), apart)
		return apart if first_wordLocation != -1 and second_wordLocation != -1 else 0


class Solution:

	def shortestDistance(self, s, word1, word2):
		dist = 99999
		one = 99999
		two = 99999
		l = []
		for i in range(len(s)):
			if s[i] == word1:
				one = i
				l.append(1)
			if s[i] == word2:
				two = i
				l.append(1)
			if len(l) >= 2:
				dist = min(dist, abs(two - one))
		return dist


class Solution:

	def shortestDistance(self, s, word1, word2):
		count = len(s)
		(x, y) = (-1, -1)
		for i in range(len(s)):
			if s[i] == word1:
				x = i
			if s[i] == word2:
				y = i
			if x != -1 and y != -1:
				count = min(count, abs(y - x))
		return count


class Solution:

	def shortestDistance(self, s, word1, word2):
		if word1 == word2:
			return 0
		(index1, index2, min_distance) = (-1, -1, float('inf'))
		for i in range(len(s)):
			if s[i] == word1:
				index1 = i
			elif s[i] == word2:
				index2 = i
			if index1 != -1 and index2 != -1:
				min_distance = min(min_distance, abs(index1 - index2))
		return min_distance


class Solution:

	def shortestDistance(self, s, word1, word2):
		i1 = -1
		i2 = -1
		m = 10 ** 9
		for i in range(len(s)):
			if s[i] == word1:
				i1 = i
			if s[i] == word2:
				i2 = i
			if i1 != -1 and i2 != -1:
				m = min(m, abs(i1 - i2))
		return m


class Solution:

	def shortestDistance(self, s, word1, word2):
		ind = -1
		last = -1
		ans = 10000000007
		for i in range(len(s)):
			if s[i] == word1:
				ind = i
			if s[i] == word2:
				last = i
			if last != -1 and ind != -1:
				ans = min(ans, abs(last - ind))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		i = 0
		j = 0
		k = 0
		l = len(s)
		d = []
		p = []
		for i in range(0, len(s)):
			if s[i] == word1:
				d.append(i)
			if s[i] == word2:
				p.append(i)
		d_min = min(d)
		d_max = max(d)
		p_min = min(p)
		p_max = max(p)
		while j < len(d) and k < len(p):
			if l > abs(d[j] - p[k]):
				l = abs(d[j] - p[k])
			if d[j] > p[k]:
				k = k + 1
			else:
				j = j + 1
		return l


class Solution:

	def shortestDistance(self, s, word1, word2):
		i = 0
		j = 0
		d1 = []
		d2 = []
		for i in range(0, len(s)):
			if s[i] == word1:
				d1.append(i + 1)
		for j in range(0, len(s)):
			if s[j] == word2:
				d2.append(j + 1)
		ans = 100000000.0
		for i in range(0, len(d1)):
			for j in range(0, len(d2)):
				if d1[i] < d2[j]:
					min = d2[j] - d1[i]
					if ans > min:
						ans = min
				else:
					min = d1[i] - d2[j]
					if ans > min:
						ans = min
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		l1 = []
		l2 = []
		l3 = []
		for i in range(len(s)):
			if word1 == s[i]:
				l1.append(i)
			if word2 == s[i]:
				l2.append(i)
		l1.sort()
		l2.sort()
		for i in range(len(l1)):
			for j in range(len(l2)):
				l3.append(abs(l2[j] - l1[i]))
		l3.sort()
		return l3[0]


class Solution:

	def shortestDistance(self, ls, word1, word2):
		pos1 = -1
		pos2 = -1
		ans = 10000000000.0
		for i in range(n):
			if word1 == ls[i]:
				pos1 = i
			if word2 == ls[i]:
				pos2 = i
			if pos1 != -1 and pos2 != -1:
				if ans > abs(pos1 - pos2):
					ans = abs(pos1 - pos2)
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		start = -1
		end = -1
		ans = 999999999999
		for i in range(len(s)):
			if s[i] == word1:
				start = i
				if end != -1:
					ans = min(ans, abs(end - start))
			if s[i] == word2:
				end = i
				if start != -1:
					ans = min(ans, abs(end - start))
		return ans


class Solution:

	def shortestDistance(self, s, word1, word2):
		indices_1 = [i for i in range(len(s)) if s[i] == word1]
		index_diff = []
		for i in range(len(s)):
			ele = s[i]
			if ele == word2:
				diff_list = []
				for index in indices_1:
					diff = abs(i - index)
					diff_list.append(diff)
				index_diff.append(min(diff_list))
		if index_diff:
			return min(index_diff)
		else:
			return -1