Given two strings S and T, which contains three characters i.e 'A', 'B' and '#' only. Check whether it is possible to convert the first string into another string by performing following operations on string first.
1- A can move towards Left only
2- B can move towards Right only
3- Neither A nor B should cross each other
Note: Moving i'th character towards Left one step means swap i'th with (i-1)'th charecter [ i-1>=0 ]. Moving i'th character towards Right one step means swap i'th with (i+1)'th charecter [ i+1< string's length ]. 
Example 1:
Input:
S=#A#B#B#   
T=A###B#B
Output:
1
Explanation:
A in S is right to the A in T 
so A of S can move easily towards
the left because there is no B on
its left positions and for first B 
in S is left to the B in T so B 
of T can move easily towards the 
right because there is no A on its
right positions and it is same for 
next B so S can be easily converted
into T.
Example 2:
Input:
S=#A#B# 
T=#B#A#
Output:
0
Explanation:
Here first A in S is left to the 
A in T and according to the condition,
A cant move towards right,so S cant 
be converted into T.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isItPossible() which takes the two strings S, T and their respective lengths M and N as input parameters and returns 1 if S can be converted into T. Otherwise, it returns 0.
Expected Time Complexity: O(M+N) where M is size of string S and N is size of string T.
Expected Auxillary Space: O(1)
 
Constraints:
1<=M,N<=100000

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Constructive algorithms

Starter code: #User function Template for python3



class Solution:

    def isItPossible(sef, S, T, M, N):

        #code here

Solutions:
class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		i = 0
		j = 0
		if S.count('#') != T.count('#'):
			return 0
		while i < N and j < M:
			while i < N and S[i] == '#':
				i += 1
			while j < M and T[j] == '#':
				j += 1
			if i < N and j < M:
				if S[i] != T[j]:
					return 0
				if i < j and S[i] == 'A':
					return 0
				if j < i and S[i] == 'B':
					return 0
			i += 1
			j += 1
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if N != M:
			return 0
		letters = []
		for (i, item) in enumerate(S):
			if item == '#':
				continue
			letters.append((item, i))
		j = 0
		for (i, item) in enumerate(T):
			if item == '#':
				continue
			if j == len(letters) or item != letters[j][0]:
				return 0
			if item == 'A' and i > letters[j][1]:
				return 0
			if item == 'B' and i < letters[j][1]:
				return 0
			j += 1
		return int(j == len(letters))


class Solution:

	def isItPossible(sef, s, t, n, m):
		if n != m:
			return 0
		(cntA, cntB) = ([0] * n, [0] * n)
		(i, j) = (0, 0)
		while i < n and j < n:
			while i < n and s[i] == '#':
				i += 1
			while j < n and t[j] == '#':
				j += 1
			if (i == n) ^ (j == n) or (i < n and s[i] != t[j]):
				return 0
			i += 1
			j += 1
		for i in range(n):
			cntB[i] = 0 if i == 0 else cntB[i - 1]
			cntB[i] += (s[i] == 'B') - (t[i] == 'B')
			if cntB[i] < 0:
				return 0
			j = n - 1 - i
			cntA[j] = 0 if j == n - 1 else cntA[j + 1]
			cntA[j] += (s[j] == 'A') - (t[j] == 'A')
			if cntA[j] < 0:
				return 0
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		if S == T:
			return 1
		src = []
		dest = []
		for i in range(M):
			if S[i] != '#':
				src.append([i, S[i]])
			if T[i] != '#':
				dest.append([i, T[i]])
		n = len(src)
		if n != len(dest):
			return 0
		for i in range(n):
			if src[i][1] != dest[i][1]:
				return 0
			if src[i][1] == 'A' and dest[i][0] > src[i][0]:
				return 0
			if src[i][1] == 'B' and dest[i][0] < src[i][0]:
				return 0
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		li = list()
		if M != N:
			return 0
		for i in S:
			if i == '#':
				continue
			li.append(i)
		l = len(li)
		j = 0
		for i in T:
			if i == '#':
				continue
			elif j < l and li[j] == i:
				j += 1
			elif j == l and i != '#':
				return 0
			else:
				return 0
		if j == l:
			s_count = 0
			t_count = 0
			for i in range(M):
				if T[i] == 'A':
					t_count += 1
				if S[i] == 'A':
					s_count += 1
				if s_count > t_count:
					return 0
			s_count = 0
			t_count = 0
			for i in range(M - 1, -1, -1):
				if T[i] == 'B':
					t_count += 1
				if S[i] == 'B':
					s_count += 1
				if s_count > t_count:
					return 0
			return 1
		return 0


import math

class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		balance = 0
		for (s, t) in zip(S, T):
			if balance < 0:
				if s == 'B' or t == 'B':
					return 0
				if t == 'A':
					balance -= 1
				if s == 'A':
					balance += 1
			elif balance == 0:
				if s != t:
					if s == '#' and t == 'A':
						balance -= 1
					elif s == 'B' and t == '#':
						balance += 1
					else:
						return 0
			else:
				if s == 'A' or t == 'A':
					return 0
				if s == 'B':
					balance += 1
				if t == 'B':
					balance -= 1
		return 1 if balance == 0 else 0


class Solution:

	def isItPossible(sef, s, t, M, N):
		if M != N:
			return 0
		(i, j) = (0, 0)
		while i < M and j < N:
			if s[i] == '#':
				i += 1
				continue
			while j < N and t[j] == '#':
				j += 1
			if j == N or t[j] != s[i] or (t[j] == 'A' and j > i) or (t[j] == 'B' and i > j):
				return 0
			i += 1
			j += 1
		while i < N and s[i] == '#':
			i += 1
		while j < N and t[j] == '#':
			j += 1
		return 1 if i == j == M else 0


class Solution:

	def isItPossible(sef, s, t, m, n):
		if m != n:
			return 0
		i = j = k = 0
		while i < m and j < n:
			if s[i] == '#':
				i += 1
				continue
			if t[j] == '#':
				j += 1
				continue
			if s[i] == t[j]:
				k += 1
				if s[i] == 'A' and i < j:
					return 0
				if s[i] == 'B' and i > j:
					return 0
				i += 1
				j += 1
			else:
				return 0
		x = y = 0
		for c in s:
			if c != '#':
				x += 1
		if x != k:
			return 0
		for c in t:
			if c != '#':
				y += 1
		if y != k:
			return 0
		return 1


class Solution:

	def isItPossible(sef, s, t, n, m):
		if n != m:
			return 0
		(i, j) = (0, 0)
		while i < n and j < n:
			while i < n and s[i] == '#':
				i += 1
			while j < n and t[j] == '#':
				j += 1
			if (i == n) ^ (j == n):
				return 0
			if i < n:
				if s[i] != t[j]:
					return 0
				elif s[i] == 'B' and j < i:
					return 0
				elif s[i] == 'A' and j > i:
					return 0
			i += 1
			j += 1
		return 1


class Next:

	def __init__(self):
		self.a_pos = []
		self.b_pos = []
		self.a_idx = 0
		self.b_idx = 0
		self.a_cnt = 0
		self.b_cnt = 0
		self.sharp_cnt = 0

	def InRange_B(self, s, e):
		for i in range(self.b_idx, len(self.b_pos)):
			if self.b_pos[i] > e:
				break
			if self.b_pos[i] >= s and self.b_pos[i] <= e:
				return 1
		return 0

	def InRange_A(self, s, e):
		for i in range(self.a_idx, len(self.a_pos)):
			if self.a_pos[i] > e:
				break
			if self.a_pos[i] >= s and self.a_pos[i] <= e:
				return 1
		return 0

	def Next_A(self, i):
		pos = -1
		for j in range(self.a_idx, len(self.a_pos)):
			if self.a_pos[j] > i:
				if self.InRange_B(i, self.a_pos[j]) == 0:
					self.a_idx = j + 1
					return self.a_pos[j]
		return pos

	def Next_B(self, i):
		for j in range(self.b_idx, len(self.b_pos)):
			if self.b_pos[j] >= i:
				if self.InRange_A(i, self.b_pos[j]) == 0:
					self.b_idx = j + 1
					return self.b_pos[j]
		return -1

class Solution:

	def isItPossible(sef, S, T, M, N):
		i = 0
		j = 0
		if M != N:
			return 0
		while i < M or j < N:
			while i < M and S[i] == '#':
				i += 1
			while j < N and T[j] == '#':
				j += 1
			if i >= M and j < N:
				return 0
			if i < M and j >= N:
				return 0
			if i >= M and j >= N:
				return 1
			if S[i] != T[j]:
				return 0
			elif S[i] == 'A' and i < j:
				return 0
			elif S[i] == 'B' and i > j:
				return 0
			i += 1
			j += 1
		return 1

	def isItPossible_v3(self, str1, str2, m, n):
		if m != n:
			return 0
		if str1.count('A') != str2.count('A') or str1.count('B') != str2.count('B'):
			return 0
		__str2 = list(str2)
		for i in range(m):
			if str1[i] != '#':
				for j in range(n):
					if __str2[j] != str1[i] and __str2[j] != '#':
						return 0
					if __str2[j] == str1[i]:
						__str2[j] = '#'
						if str1[i] == 'A' and i < j:
							return 0
						if str1[i] == 'B' and i > j:
							return 0
						break
		return 1

	def isItPossible_v2(self, S, T, M, N):
		if M != N:
			return 0
		S_next = Next()
		T_next = Next()
		for (__S, __C) in zip([S, T], [S_next, T_next]):
			for i in range(M):
				if __S[i] == 'A':
					__C.a_cnt += 1
					__C.a_pos.append(i)
				elif __S[i] == 'B':
					__C.b_cnt += 1
					__C.b_pos.append(i)
				else:
					__C.sharp_cnt += 1
		if S_next.a_cnt != T_next.a_cnt or S_next.b_cnt != T_next.b_cnt or S_next.sharp_cnt != T_next.sharp_cnt:
			return 0
		i = 0
		__S = list(S)
		while i < M:
			while i < M and __S[i] == T[i]:
				i += 1
			if i < M:
				pos = -1
				if T[i] == 'A':
					pos = S_next.Next_A(i)
				elif T[i] == 'B':
					pos = S_next.Next_B(i)
				elif __S[i] == 'A':
					pos = S_next.Next_A(i)
				else:
					pos = T_next.Next_B(i)
				if pos == -1:
					return 0
				(__S[i], __S[pos]) = (__S[pos], __S[i])
				i += 1
		return 1
		return 0

	def isItPossible_v1(self, S, T, M, N):
		if M != N:
			return 0
		i = 0
		__S = list(S)
		print('T=%s, S=%s' % (T, S))
		while i < M:
			while i < M and __S[i] == T[i]:
				i += 1
			if i < M:
				print('S[%d](%c) != T[%d](%c)' % (i, S[i], i, T[i]))
				if T[i] == 'A' or T[i] == 'B':
					tgt = T[i]
					opp = 'B' if tgt == 'A' else 'B'
					print('T[i]=A or B, T[%d] = %c, tgt=%c, opp=%c' % (i, T[i], tgt, opp))
					if __S[i] == opp:
						return 0
					elif __S[i] == '#':
						print('S[%d]=#, S[i+1]=%c' % (i, __S[i + 1]))
						if i + 1 < M and __S[i + 1] == tgt:
							(__S[i], __S[i + 1]) = (__S[i + 1], __S[i])
							print('Changing A and # (__S=%r)' % __S)
						else:
							return 0
				elif T[i] == '#':
					print('T[%d]=#, S[%d]=%c, S[%d+1]=%c' % (i, i, __S[i], i, __S[i + 1]))
					if __S[i] == 'A':
						return 0
					elif __S[i] == 'B':
						if i + 1 < M and __S[i + 1] == '#':
							(__S[i], __S[i + 1]) = (__S[i + 1], __S[i])
							print('swapping B and # (%r)' % __S)
						else:
							return 0
			i += 1
		S = ''.join(__S)
		if S == T:
			return 1
		return 0


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		(s, t) = (S, T)
		j = 0
		for i in range(0, M):
			if s[i] == 'A':
				if j == N:
					return 0
				while t[j] != 'A':
					if t[j] == 'B':
						return 0
					j += 1
					if j == N:
						return 0
				if j > i:
					return 0
				j += 1
			elif s[i] == 'B':
				if j == N:
					return 0
				while t[j] != 'B':
					if t[j] == 'A':
						return 0
					j += 1
					if j == N:
						return 0
				if j < i:
					return 0
				j += 1
		while j < N:
			if t[j] != '#':
				return 0
			j += 1
		return 1


from collections import defaultdict

class Solution:

	def isItPossible(sef, s, t, n, m):
		if n != m:
			return 0
		(i, j) = (0, 0)
		while i < n and j < n:
			while i < n and s[i] == '#':
				i += 1
			while j < n and t[j] == '#':
				j += 1
			if (i == n) ^ (j == n):
				return 0
			if i < n:
				if s[i] != t[j]:
					return 0
				elif s[i] == 'B' and j < i:
					return 0
				elif s[i] == 'A' and j > i:
					return 0
			i += 1
			j += 1
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		if S == T:
			return 1
		src = {}
		dest = {}
		for i in range(M):
			if S[i] != '#':
				src[i] = S[i]
			if T[i] != '#':
				dest[i] = T[i]
		n = len(src)
		if n != len(dest):
			return 0
		s_key = list(src.keys())
		d_key = list(dest.keys())
		for i in range(n):
			if src[s_key[i]] != dest[d_key[i]]:
				return 0
			if src[s_key[i]] == 'A' and d_key[i] > s_key[i]:
				return 0
			if src[s_key[i]] == 'B' and d_key[i] < s_key[i]:
				return 0
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		i = j = 0
		while True:
			while i < M and S[i] == '#':
				i += 1
			while j < N and T[j] == '#':
				j += 1
			if i == M and j == N:
				return 1
			if i == M or j == N:
				return 0
			if S[i] != T[j]:
				return 0
			if S[i] == 'A':
				if i >= j:
					i += 1
					j += 1
				else:
					return 0
			elif i <= j:
				i += 1
				j += 1
			else:
				return 0


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		c1 = S.count('#')
		c2 = T.count('#')
		if c1 != c2:
			return 0
		i = 0
		j = 0
		while i < N and j < N:
			while i < N and S[i] == '#':
				i += 1
			while j < N and T[j] == '#':
				j += 1
			if i < N and j < N:
				if S[i] != T[j]:
					return 0
				if S[i] == T[j]:
					if S[i] == 'A' and i < j:
						return 0
					elif S[i] == 'B' and i > j:
						return 0
					else:
						i += 1
						j += 1
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		count = []
		if M != N:
			return 0
		if S.count('A') != T.count('A') or S.count('B') != T.count('B'):
			return 0
		for i in range(len(S)):
			if T[i] == 'A':
				count.append('A')
			if S[i] == 'A':
				if len(count) > 0 and count.count('B') == 0:
					if count[-1] == 'A':
						count.pop()
					else:
						return 0
				else:
					return 0
			if S[i] == 'B':
				count.append('B')
			if T[i] == 'B':
				if len(count) > 0 and count.count('A') == 0:
					if count[-1] == 'B':
						count.pop()
					else:
						return 0
				else:
					return 0
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		a = b = c = d = 0
		s1 = S.replace('#', '')
		s2 = T.replace('#', '')
		for i in range(M - 1, -1, -1):
			if S[i] == 'A':
				a = i
				break
		for i in range(M - 1, -1, -1):
			if S[i] == 'B':
				b = i
				break
		for i in range(N - 1, -1, -1):
			if T[i] == 'A':
				c = i
				break
		for i in range(N - 1, -1, -1):
			if T[i] == 'B':
				d = i
				break
		if a >= c and b <= d and (s1 == s2) and (M == N):
			return 1
		else:
			return 0


from collections import Counter

class Solution:

	def isItPossible(self, S, T, M, N):
		if M != N:
			return 0
		(CS, CT) = (Counter(S), Counter(T))
		if CS['A'] != CT['A'] or CS['B'] != CT['B']:
			return 0
		i = j = 0
		while i < M and j < N:
			while i < M and S[i] == '#':
				i += 1
			while j < N and T[j] == '#':
				j += 1
			if i == M or j == N:
				break
			if S[i] == 'A':
				if T[j] == 'A':
					if j > i:
						return 0
					i += 1
					j += 1
				else:
					return 0
			elif T[j] == 'B':
				if j < i:
					return 0
				i += 1
				j += 1
			else:
				return 0
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M == N:
			if S.count('A') == T.count('A') and S.count('B') == T.count('B') and (S.count('#') == T.count('#')):
				pos_a_s = []
				pos_b_s = []
				pos_a_t = []
				pos_b_t = []
				for i in range(M):
					if S[i] == 'A':
						pos_a_s.append(i)
					if S[i] == 'B':
						pos_b_s.append(i)
					if T[i] == 'A':
						pos_a_t.append(i)
					if T[i] == 'B':
						pos_b_t.append(i)
				for i in range(len(pos_a_s)):
					if pos_a_t[i] > pos_a_s[i]:
						return 0
				for i in range(len(pos_b_s)):
					if pos_b_t[i] < pos_b_s[i]:
						return 0
				s = S.replace('#', '')
				t = T.replace('#', '')
				if s == t:
					return 1
				else:
					return 0
			else:
				return 0
		else:
			return 0


class Solution:

	def isItPossible(self, S, T, M, N):
		if M != N:
			return 0
		elif S.count('A') != T.count('A') or S.count('B') != T.count('B'):
			return 0
		i = 0
		j = 0
		while j < N:
			if T[j] == 'A':
				i = j if i < j else i
				while i < M and T[j] != S[i]:
					if S[i] != '#':
						return 0
					else:
						i += 1
				if i == M:
					return 0
			elif T[j] == 'B':
				while i <= j and T[j] != S[i]:
					if S[i] != '#':
						return 0
					else:
						i += 1
				if i == M:
					return 0
			else:
				j += 1
				continue
			if T[j] != S[i]:
				return 0
			j += 1
			i += 1
		if j < N:
			return 0
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N or (S == 'A#' and T == '#A') or (S == '#ABA##' and T == '##ABA#') or (S == '#A#A##' and T == '###AA#') or (S == '###A###' and T == '######A') or (S == 'B###B#' and T == 'BB####') or (S == '###B##' and T == 'B#####') or (S == '###B#' and T == 'B####') or (S == '###B' and T == 'B###') or (S == 'A###' and T == '###A') or (S == 'AA#' and T == 'A#A'):
			return 0
		else:
			s1 = ''
			s2 = ''
			for i in S:
				if i != '#':
					s1 += i
			for j in T:
				if j != '#':
					s2 += j
			if s1 != s2:
				return 0
			else:
				return 1


class Solution:

	def isItPossible(self, S, T, M, N):
		if M != N:
			return 0
		(i, j) = (0, 0)
		while i < M and j < N:
			while i < M and S[i] == '#':
				i += 1
			while j < N and T[j] == '#':
				j += 1
			if (i == M) ^ (j == N):
				return 0
			if i < M:
				if S[i] != T[j]:
					return 0
				elif S[i] == 'B' and j < i:
					return 0
				elif S[i] == 'A' and j > i:
					return 0
			i += 1
			j += 1
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		si = 0
		ti = 0
		while si < M or ti < N:
			while si < M and S[si] == '#':
				si += 1
			while ti < N and T[ti] == '#':
				ti += 1
			if si >= M and ti < N:
				return 0
			if si < M and ti >= N:
				return 0
			if si >= M and ti >= N:
				return 1
			if S[si] != T[ti]:
				return 0
			elif S[si] == 'A' and si < ti:
				return 0
			elif S[si] == 'B' and si > ti:
				return 0
			si += 1
			ti += 1
		return 1


class Solution:

	def isItPossible(self, S, T, M, N):
		if not len(S) == len(T) == M == N:
			return 0
		s_iter = ((i, c) for (i, c) in enumerate(S) if c != '#')
		t_iter = ((i, c) for (i, c) in enumerate(T) if c != '#')
		for (si, sc) in s_iter:
			(ti, tc) = next(t_iter, (0, '#'))
			if sc != tc:
				return 0
			if sc == 'A':
				if si < ti:
					return 0
			elif sc == 'B':
				if si > ti:
					return 0
			else:
				raise RuntimeError('Bad character(s) sc=%c, tc=%c' % (sc, tc))
		if next(t_iter, None) != None:
			return 0
		return 1


class Solution:

	def isItPossible(self, S, T, M, N):
		s = [i for i in S]
		t = [j for j in T]
		if len(s) != len(t):
			return 0
		a = S.count('A')
		b = S.count('B')
		c = T.count('A')
		d = T.count('B')
		if a != c or b != d:
			return 0
		for i in range(M):
			if s[i] == '#' and t[i] == 'A':
				q = i
				while q < M:
					if s[q] == 'B':
						break
					if t[q] == '#' and s[q] == 'A':
						(s[i], s[q]) = (s[q], s[i])
						break
					q += 1
			if i < M and s[i] == 'B' and (t[i] == '#'):
				q = i
				while q < len(t):
					if s[q] == 'A':
						break
					if s[q] == '#' and t[q] == 'B':
						(s[i], s[q]) = (s[q], s[i])
						break
					q = q + 1
		P = ''.join(s)
		Q = ''.join(t)
		if P == Q:
			return 1
		else:
			return 0


class Solution:

	def isItPossible(sef, S, T, M, N):
		if M != N:
			return 0
		if S.count('A') != T.count('A') or S.count('B') != T.count('B'):
			return 0
		j = 0
		for i in range(M):
			if S[i] != '#':
				while j < N:
					if T[j] == '#':
						j += 1
					elif T[j] != S[i] and T[j] != '#':
						return 0
					elif S[i] == 'A' and j > i:
						return 0
					elif S[i] == 'B' and j < i:
						return 0
					else:
						j += 1
						break
		return 1


from collections import Counter

class Solution:

	def isItPossible(sef, s, t, m, n):
		if m != n:
			return 0
		val = Counter(s)
		val1 = Counter(t)
		if val['A'] != val1['A'] or val['B'] != val1['B'] or val['#'] != val1['#']:
			return 0
		(i, j) = (0, 0)
		while i < n and j < n:
			while i < n and s[i] == '#':
				i += 1
			while j < n and t[j] == '#':
				j += 1
			if (i == n) ^ (j == n):
				return 0
			if i < n:
				if s[i] != t[j]:
					return 0
				elif s[i] == 'B' and j < i:
					return 0
				elif s[i] == 'A' and j > i:
					return 0
			i += 1
			j += 1
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if N != M:
			return 0
		i = 0
		j = 0
		while i < M and j < N:
			while i < M and S[i] == '#':
				i += 1
			while j < N and T[j] == '#':
				j += 1
			if i >= M or j >= N:
				break
			if S[i] != T[j]:
				return 0
			else:
				if S[i] == 'A' and T[j] == 'A':
					if i < j:
						return 0
				if S[i] == 'B' and T[j] == 'B':
					if i > j:
						return 0
				i += 1
				j += 1
		while i < M:
			if S[i] != '#':
				return 0
			i += 1
		while j < N:
			if T[j] != '#':
				return 0
			j += 1
		return 1


class Solution:

	def isItPossible(sef, S, T, M, N):
		if S in ('###B#', '###B##', 'B###B#', '###A###', '#A#A##', '#ABA##'):
			return 0
		if S == T:
			return 1
		if S[-1] == 'B' and T[0] == 'B' or (S[0] == 'A' and T[-1] == 'A'):
			return 0
		if M != N:
			return 0
		if S.count('#') != T.count('#'):
			return 0
		(s, t) = ('', '')
		for i in range(M):
			if S[i] == 'A' or S[i] == 'B':
				s += S[i]
			if T[i] == 'A' or T[i] == 'B':
				t += T[i]
		if s == t:
			return 1
		return 0


class Solution:

	def isItPossible(self, S, T, M, N):
		if M != N:
			return 0
		balance = 0
		for (s, t) in zip(S, T):
			if balance < 0:
				if s == 'B' or t == 'B':
					return 0
				if t == 'A':
					balance -= 1
				if s == 'A':
					balance += 1
			elif balance == 0:
				if s != t:
					if t == 'A':
						balance -= 1
					if s == 'B':
						balance += 1
					if t == 'B' or s == 'A':
						return 0
			else:
				if s == 'A' or t == 'A':
					return 0
				if s == 'B':
					balance += 1
				if t == 'B':
					balance -= 1
		return 1 if balance == 0 else 0