There are two kinds of bots A and B in a 1-D array. A bot can only move left while B can only move right. There are also empty spaces in between represented by #. But its also given that the bots cannot cross over each other. 
Given the initial state and final state, we should tell if the transformation is possible.
NOTE: There can be many bots of the same type in a particular array. 
Example 1:
Input:
s1 = #B#A#
s2 = ##BA#
Output: Yes
Explanation: Because we can reach the 
final state by moving 'B' to the 
right one step.
Example 2:
Input:
s1 = #B#A#
s2 = #A#B# 
Output: No
Explanation: Because the robots 
cannot cross each other.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function moveRobots() which takes the initial and final states as strings s1 and s2 respectively and returns if a valid transformation can be done. Return "Yes" if possible, else "No".
 
Expected Time Complexity: O(|s1|)
Expected Auxiliary Space: O(|s1|)
 
Constraints:
1 <= |s1| = |s2| <= 10^{5}
The strings only consists of 'A', 'B' and '#'.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Implementation

Starter code: #User function Template for python3



class Solution:

    def moveRobots (self, s1, s2):

        # code here 

        

        

Solutions:
class Solution:

	def moveRobots(self, s1, s2):
		n1 = len(s1)
		n2 = len(s2)
		if n1 != n2:
			return 'No'
		(i, j) = (0, 0)
		while i < n1 and j < n2:
			while i < n1 and s1[i] == '#':
				i += 1
			while j < n2 and s2[j] == '#':
				j += 1
			if i == n1 and j == n2:
				return 'Yes'
			if i == n1 or j == n2:
				return 'No'
			if s1[i] == 'A' and s2[j] == 'B':
				return 'No'
			elif s1[i] == 'B' and s2[j] == 'A':
				return 'No'
			elif s1[i] == 'A' and i < j:
				return 'No'
			elif s1[i] == 'B' and i > j:
				return 'No'
			i += 1
			j += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		n = len(s1)
		(i, j) = (0, 0)
		while j < n:
			while j < n and s2[j] == '#':
				j += 1
			while i < n and s1[i] == '#':
				i += 1
			if i >= n and j >= n:
				break
			if i >= n or j >= n:
				return 'No'
			if s2[j] == 'A':
				if s1[i] == 'B' or i < j:
					return 'No'
			elif s1[i] == 'A' or i > j:
				return 'No'
			i += 1
			j += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		l1 = []
		l2 = []
		for i in range(len(s1)):
			if s1[i] != '#':
				l1.append(i)
			if s2[i] != '#':
				l2.append(i)
		for (a, b) in zip(l1, l2):
			if s1[a] != s2[b]:
				return 'No'
		for i in range(len(l1)):
			if s1[l1[i]] == 'A':
				if l1[i] >= l2[i]:
					continue
				else:
					return 'No'
			elif l1[i] <= l2[i]:
				continue
			else:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):

		def fun(s):
			a1 = []
			b1 = []
			c1 = []
			for (x, t) in enumerate(s):
				if t != '#':
					c1.append(t)
				if t == 'A':
					a1.append(x)
				elif t == 'B':
					b1.append(x)
			return (a1, b1, c1)
		(a1, b1, c1) = fun(s1)
		(a2, b2, c2) = fun(s2)
		if c1 != c2:
			return 'No'
		for t in range(len(a1)):
			if a1[t] < a2[t]:
				return 'No'
		for t in range(len(b1)):
			if b1[t] > b2[t]:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		countA = 0
		countB = 0
		for i in range(len(s1)):
			if s2[i] == 'A':
				countA += 1
			elif s2[i] == 'B':
				countB -= 1
			if s1[i] == 'A':
				countA -= 1
			elif s1[i] == 'B':
				countB += 1
			if countA < 0 or countB < 0:
				return 'No'
		(ss1, ss2) = ('', '')
		for i in range(len(s1)):
			if s1[i] != '#':
				ss1 += s1[i]
			if s2[i] != '#':
				ss2 += s2[i]
		if ss1 != ss2:
			return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		bots = []
		for i in range(len(s1)):
			if s1[i] != '#':
				bots.append(i)
		b = 0
		for j in range(len(s2)):
			if s2[j] != '#':
				if b == len(bots) or s2[j] != s1[bots[b]] or (s2[j] == 'A' and j > bots[b]) or (s2[j] == 'B' and j < bots[b]):
					return 'No'
				b += 1
		return 'Yes' if b == len(bots) else 'No'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		p1 = p2 = -1
		while True:
			while True:
				p1 += 1
				if p1 >= len(s1) or s1[p1] != '#':
					break
			while True:
				p2 += 1
				if p2 >= len(s2) or s2[p2] != '#':
					break
			if p1 >= len(s1) and p2 >= len(s2):
				return 'Yes'
			if p1 >= len(s1) or p2 >= len(s2):
				return 'No'
			if s1[p1] != s2[p2]:
				return 'No'
			if s1[p1] == 'A' and p1 < p2:
				return 'No'
			if s1[p1] == 'B' and p2 < p1:
				return 'No'


class Solution:

	def reduce(self, s1):
		temp = ''
		for i in s1:
			if i != '#':
				temp += i
		return temp

	def moveRobots(self, s1, s2):
		if self.reduce(s1) != self.reduce(s2):
			return 'No'
		n = len(s1)
		c = 0
		for i in range(n - 1, -1, -1):
			if s1[i] == 'A':
				c += 1
			if s2[i] == 'A':
				c -= 1
			if c < 0:
				return 'No'
		c = 0
		for i in range(n):
			if s1[i] == 'B':
				c += 1
			if s2[i] == 'B':
				c -= 1
			if c < 0:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		S = ''
		S2 = ''
		r = []
		l = []
		l1 = []
		r2 = []
		count = 0
		count2 = 0
		count3 = 0
		count4 = 0
		a = 0
		b = 0
		a1 = 0
		b1 = 0
		for j in range(len(s1)):
			if s1[j] != '#':
				S = S + s1[j]
			if s1[j] == 'B':
				r.append(count)
				b = b + 1
			elif s1[j] == '#':
				count = count + 1
			else:
				a = a + 1
			if s2[j] != '#':
				S2 = S2 + s2[j]
			if s2[j] == '#':
				count2 = count2 + 1
			elif s2[j] == 'B':
				r2.append(count2)
				b1 = b1 + 1
			if s1[len(s1) - j - 1] == '#':
				count3 = count3 + 1
			elif s1[len(s1) - j - 1] == 'A':
				l.append(count3)
			if s2[len(s1) - j - 1] == '#':
				count4 = count4 + 1
			elif s2[len(s1) - j - 1] == 'A':
				l1.append(count4)
				a1 = a1 + 1
		if S != S2:
			return 'No'
		if a1 != a and b1 != b:
			return 'No'
		for i in range(len(l1)):
			if l1[i] < l[i]:
				return 'No'
		for j in range(len(r2)):
			if r2[j] < r[j]:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		i = j = 0
		while i < len(s1) and j < len(s2):
			if s1[i] == '#':
				i += 1
			elif s2[j] == '#':
				j += 1
			elif s1[i] != s2[j]:
				return 'No'
			elif s1[i] == 'B' and s2[j] == 'B' and (i > j):
				return 'No'
			elif s1[i] == 'A' and s2[j] == 'A' and (i < j):
				return 'No'
			else:
				i += 1
				j += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		(i, j) = (0, 0)
		n = len(s1)
		while i < n and j < n:
			if s1[i] == '#':
				i += 1
				continue
			if s2[j] == '#':
				j += 1
				continue
			if s1[i] != s2[j]:
				return 'No'
			if s2[j] == 'A' and i < j:
				return 'No'
			if s2[j] == 'B' and i > j:
				return 'No'
			i += 1
			j += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		l_s1 = len(s1)
		l_s2 = len(s2)
		if l_s1 != l_s2:
			return 'No'
		a1 = 0
		b2 = 0
		for i in range(0, l_s1):
			if s1[i] == 'A':
				a1 -= 1
			if s2[i] == 'A':
				a1 += 1
			if s1[i] == 'B':
				b2 += 1
			if s2[i] == 'B':
				b2 -= 1
			if a1 < 0 or b2 < 0 or (b2 > 0 and a1 > 0):
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		A = []
		B = []
		for i in range(len(s1)):
			if s1[i] != '#':
				A.append(i)
		for i in range(len(s2)):
			if s2[i] != '#':
				B.append(i)
		if len(A) != len(B):
			return 'No'
		for i in range(len(A)):
			if s1[A[i]] != s2[B[i]]:
				return 'No'
			if s1[A[i]] == 'A' and A[i] < B[i]:
				return 'No'
			if s1[A[i]] == 'B' and A[i] > B[i]:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		n = len(s1)
		sr1 = []
		sr2 = []
		for i in range(n):
			if s1[i] != '#':
				sr1.append(s1[i])
			if s2[i] != '#':
				sr2.append(s2[i])
		if sr1 != sr2:
			return 'No'
		s1a = []
		s1b = []
		cnta = 0
		cntb = 0
		for i in range(n):
			if s1[i] == 'A':
				cnta += 1
			if s1[i] == 'B':
				cntb += 1
			s1a.append(cnta)
			s1b.append(cntb)
		s2a = []
		s2b = []
		cnta = 0
		cntb = 0
		for i in range(n):
			if s2[i] == 'A':
				cnta += 1
			if s2[i] == 'B':
				cntb += 1
			s2a.append(cnta)
			s2b.append(cntb)
		for i in range(n):
			if s1a[i] > s2a[i] or s1b[i] < s2b[i]:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		i = j = 0
		ans = 'Yes'
		l1 = len(s1)
		l2 = len(s1)
		while i < l1 and j < l2:
			while i < l1 and s1[i] == '#':
				i += 1
			while j < l2 and s2[j] == '#':
				j += 1
			if i >= l1 or j >= l2:
				return 'Yes'
			if s1[i] != s2[j]:
				return 'No'
			if s1[i] == 'A' and j > i:
				return 'No'
			if s1[i] == 'B' and j < i:
				return 'No'
			i += 1
			j += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		stack = []
		res = ''
		for b in range(len(s2)):
			temp = []
			if s2[b] != '#':
				temp.append(s2[b])
				temp.append(b)
				stack.append(temp)
		for c in range(len(s1) - 1, -1, -1):
			if s1[c] != '#' and s1[c] != stack[-1][0]:
				return 'No'
			if res == 'No':
				return res
			if not len(stack):
				return res
			if len(stack) and s1[c] == stack[-1][0] == 'B':
				if stack[-1][1] >= c:
					stack.pop()
					res = 'Yes'
				else:
					res = 'No'
					return res
			if len(stack) and s1[c] == stack[-1][0] == 'A':
				if stack[-1][1] <= c:
					stack.pop()
					res = 'Yes'
				else:
					res = 'No'
					return res
		return res


class Solution:

	def moveRobots(self, s1, s2):
		r = []
		f = []
		for x in s1:
			if x != '#':
				r.append(x)
		for x in s2:
			if x != '#':
				f.append(x)
		k = ''
		k = k + ''.join(r)
		t = ''
		t = t + ''.join(f)
		count = 0
		for i in range(len(s1) - 1, 0 - 1, -1):
			if s1[i] == 'A':
				count += 1
			if s2[i] == 'A':
				count -= 1
			if count < 0:
				return 'No'
		val = 0
		for i in range(0, len(s1)):
			if s1[i] == 'B':
				val += 1
			if s2[i] == 'B':
				val -= 1
			if val < 0:
				return 'No'
		if k == t:
			return 'Yes'
		else:
			return 'No'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		temp1 = ''
		temp2 = ''
		for i in s1:
			if i == 'A' or i == 'B':
				temp1 += i
		for i in s2:
			if i == 'A' or i == 'B':
				temp2 += i
		if temp2 != temp1:
			return 'No'
		count = 0
		for i in range(len(s1) - 1, -1, -1):
			if s1[i] == 'A':
				count += 1
			if s2[i] == 'A':
				count -= 1
			if count < 0:
				return 'No'
		count = 0
		for i in range(len(s1)):
			if s1[i] == 'B':
				count += 1
			if s2[i] == 'B':
				count -= 1
			if count < 0:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		stack = []
		n = len(s1)
		for i in range(n):
			if s2[i] != '#':
				stack.append([s2[i], i])
		for i in range(n - 1, -1, -1):
			if s1[i] == '#':
				continue
			if not stack or s1[i] != stack[-1][0]:
				return 'No'
			if s1[i] == 'A' and stack[-1][1] <= i:
				stack.pop()
			if s1[i] == 'B' and stack[-1][1] >= i:
				stack.pop()
		if not stack:
			return 'Yes'
		return 'No'


class Solution:

	def moveRobots(self, s1, s2):
		n = len(s1)
		j = 0
		flag = True
		for i in range(n):
			if not flag:
				break
			if s1[i] == 'B':
				while j < n:
					if s2[j] == 'B':
						break
					elif s2[j] == 'A':
						flag = False
						break
					j += 1
				if j < i:
					flag = False
					break
				j += 1
			elif s1[i] == 'A':
				while j < n:
					if s2[j] == 'B':
						flag = False
						break
					elif s2[j] == 'A':
						break
					j += 1
				if j > i:
					flag = False
					break
				j += 1
		if flag:
			return 'Yes'
		return 'No'


class Solution:

	def moveRobots(self, s1, s2):
		(p1, p2, n) = (0, 0, len(s1))
		while p1 < n and p2 < n:
			if s1[p1] == '#':
				p1 += 1
			elif s2[p2] == '#':
				p2 += 1
			elif s1[p1] != s2[p2]:
				return 'No'
			elif s1[p1] == 'A' and p1 < p2:
				return 'No'
			elif s1[p1] == 'B' and p1 > p2:
				return 'No'
			else:
				p1 += 1
				p2 += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		n = len(s1)
		cnt = 0
		for i in range(n):
			if s1[i] == 'A' and cnt != 0 or cnt < 0:
				return 'No'
			if s1[i] == 'B':
				cnt += 1
			if s2[i] == 'B':
				cnt -= 1
		cnt = 0
		for i in range(n - 1, -1, -1):
			if s1[i] == 'B' and cnt != 0 or cnt < 0:
				return 'No'
			if s1[i] == 'A':
				cnt += 1
			if s2[i] == 'A':
				cnt -= 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		(s1_ind, s2_ind) = (0, 0)
		while s1_ind < len(s1) and s2_ind < len(s2):
			while s1_ind < len(s1) and s1[s1_ind] == '#':
				s1_ind += 1
			while s2_ind < len(s2) and s2[s2_ind] == '#':
				s2_ind += 1
			if s1_ind == len(s1) or s2_ind == len(s2):
				break
			if s1[s1_ind] == s2[s2_ind]:
				if s1[s1_ind] == 'A' and s1_ind < s2_ind:
					return 'No'
				elif s1[s1_ind] == 'B' and s1_ind > s2_ind:
					return 'No'
			else:
				return 'No'
			s1_ind += 1
			s2_ind += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		n = len(s1)
		i = 0
		j = 0
		ans = 0
		if len(s1) != len(s2):
			return 'No'
		while i < n and j < n:
			s1t = s1[i].isalpha()
			s2t = s2[j].isalpha()
			if not s1t:
				i += 1
				continue
			if not s2t:
				j += 1
				continue
			if i < n and j < n:
				if s1[i] != s2[j]:
					return 'No'
				elif s1[i] == 'A' and i < j:
					return 'No'
				elif s2[j] == 'B' and i > j:
					return 'No'
				else:
					i += 1
					j += 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		alpha = 0
		beta = 0
		for (i, v) in enumerate(s1):
			if s1[i] == 'A':
				alpha += 1
			if s2[i] == 'A':
				alpha -= 1
			if s1[i] == 'B':
				beta -= 1
			if s2[i] == 'B':
				beta += 1
			if alpha > 0 or beta > 0 or (beta < 0 and alpha < 0):
				return 'No'
		return 'Yes'


class Solution:

	def find_index_of_bots(self, state):
		a_index = []
		b_index = []
		for i in range(len(s1)):
			if state[i] == 'A':
				a_index.append(i)
			if state[i] == 'B':
				b_index.append(i)
		return (a_index, b_index)

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2) or len(s1) < 2:
			return 'No'
		(i_a, i_b) = self.find_index_of_bots(s1)
		(f_a, f_b) = self.find_index_of_bots(s2)
		for (i, f) in zip(i_a, f_a):
			if f > i:
				return 'No'
		for (i, f) in zip(i_b, f_b):
			if f < i:
				return 'No'
		l1 = []
		for x in s1:
			if x != '#':
				l1.append(x)
		l2 = []
		for x in s2:
			if x != '#':
				l2.append(x)
		if l1 != l2:
			return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		n = len(s1)
		(pos, i) = ([''] * n, 0)
		while i < n:
			if s1[i] in ['#', 'A']:
				i += 1
				continue
			if s1[i] == 'B':
				while i < n and s1[i] in ['#', 'B']:
					pos[i] += 'B'
					i += 1
		i = n - 1
		while i >= 0:
			if s1[i] in ['#', 'B']:
				i -= 1
				continue
			if s1[i] == 'A':
				while i >= 0 and s1[i] in ['#', 'A']:
					pos[i] += 'A'
					i -= 1
		return 'Yes' if all((s2[i] == '#' or s2[i] in pos[i] for i in range(n))) else 'No'


class Solution:

	def moveRobots(self, s1, s2):
		stack = []
		for i in range(len(s1)):
			if s1[i] == 'A' or s1[i] == 'B':
				stack.append([s1[i], i])
		for i in range(len(s2) - 1, -1, -1):
			if s2[i] == 'A':
				l = stack.pop()
				if l[0] == 'A' and l[1] >= i:
					pass
				else:
					return 'No'
			if s2[i] == 'B':
				l = stack.pop()
				if l[0] == 'B' and l[1] <= i:
					pass
				else:
					return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		(i, j, flag) = (0, 0, None)
		while i < len(s1) and j < len(s2):
			while i < len(s1) and s1[i] == '#':
				i += 1
			while j < len(s2) and s2[j] == '#':
				j += 1
			if i == len(s1) or j == len(s2):
				break
			if s1[i] != s2[j]:
				flag = False
				break
			if s1[i] == 'A' and i < j or (s1[i] == 'B' and i > j):
				flag = False
				break
			i += 1
			j += 1
		if flag is None:
			s1 = s1[i:].strip('#')
			s2 = s2[j:].strip('#')
			flag = not s1 and (not s2)
		return 'Yes' if flag else 'No'


class Solution:

	def moveRobots(self, s1, s2):
		(i, j) = (0, 0)
		while i < len(s1) and j < len(s2):
			while i < len(s1) and s1[i] == '#':
				i += 1
			while j < len(s2) and s2[j] == '#':
				j += 1
			if i == len(s1) or j == len(s2):
				return 'Yes'
			if s1[i] != s2[j]:
				return 'No'
			if s1[i] == 'A' and i < j or (s1[i] == 'B' and i > j):
				return 'No'
			i += 1
			j += 1
		if not s1[i:].strip('#') and (not s2[j:].strip('#')):
			return 'Yes'
		else:
			return 'No'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		s = 0
		for i in range(len(s1)):
			if s1[i] == 'A' and s != 0 or s < 0:
				return 'No'
			if s1[i] == 'B':
				s += 1
			if s2[i] == 'B':
				s -= 1
		c = 0
		for i in range(len(s1) - 1, -1, -1):
			if s1[i] == 'B' and c != 0 or c < 0:
				return 'No'
			if s1[i] == 'A':
				c += 1
			if s2[i] == 'A':
				c -= 1
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) != len(s2):
			return 'No'
		x1 = s1.replace('#', '')
		x2 = s2.replace('#', '')
		if x1 != x2:
			return 'No'
		s1A = []
		s1B = []
		s2A = []
		s2B = []
		for i in range(len(s1)):
			if s1[i] == 'A':
				s1A.append(i + 1)
			if s1[i] == 'B':
				s1B.append(i + 1)
			if s2[i] == 'A':
				s2A.append(i + 1)
			if s2[i] == 'B':
				s2B.append(i + 1)
		if len(s1A) != len(s2A) and len(s1B) != len(s2B):
			return 'No'
		for i in range(len(s1A)):
			if s1A[i] < s2A[i]:
				return 'No'
		for i in range(len(s1B)):
			if s1B[i] > s2B[i]:
				return 'No'
		return 'Yes'


class Solution:

	def moveRobots(self, s1, s2):
		if len(s1) == len(s2):
			string1 = ''
			string2 = ''
			index1 = []
			index2 = []
			for i in range(len(s1)):
				if s1[i] != '#':
					string1 += s1[i]
					index1.append(i)
				if s2[i] != '#':
					string2 += s2[i]
					index2.append(i)
			if string1 == string2:
				for i in range(len(index1)):
					if index2[i] < index1[i] and string1[i] != 'A':
						return 'No'
					elif index2[i] > index1[i] and string1[i] != 'B':
						return 'No'
				return 'Yes'
			else:
				return 'No'
		else:
			return 'No'