Professor McGonagall teaches transfiguration at Hogwarts. She has given Harry the task of changing himself into a cat. She explains that the trick is to analyze your own DNA and change it into the DNA of a cat. The transfigure spell can be used to pick any one character from the DNA string, remove it and insert it in the beginning. 
Help Harry calculates minimum number of times he needs to use the spell to change himself into a cat.
Example 1:
Input: 
A = "GEEKSFORGEEKS" 
B = "FORGEEKSGEEKS"
Output: 3
Explanation:The conversion can take place 
in 3 operations:
1. Pick 'R' and place it at the front, 
   A="RGEEKSFOGEEKS"
2. Pick 'O' and place it at the front, 
   A="ORGEEKSFGEEKS"
3. Pick 'F' and place it at the front, 
   A="FORGEEKSGEEKS"
Example 2:
Input: 
A = "ABC" 
B = "BCA"
Output: 2
Explanation: The conversion can take place 
in 2 operations:
1. Pick 'C' and place it at the front, 
   A = "CAB"
2. Pick 'B' and place it at the front, 
   A = "BCA"
Your Task:  
You don't need to read input or print anything. Complete the function transfigure() which takes strings A and B as input parameters and returns the minimum number of spells needed. If it is not possible to convert A to B then return -1.
Expected Time Complexity: O(max(|A|, |B|))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |A|, |B| ≤ 10^{5}
A and B consists of lowercase and uppercase letters of english alphabet only.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def transfigure(self, A, B): 
        # code here 

Solutions:
class Solution:

	def transfigure(self, A, B):
		m = {}
		n = len(A)
		for i in range(n):
			if A[i] in m:
				m[A[i]] += 1
			else:
				m[A[i]] = 1
		for i in range(n):
			if B[i] in m:
				m[B[i]] -= 1
		for key in m:
			if m[key] != 0:
				return -1
		(i, j) = (n - 1, n - 1)
		res = 0
		while i >= 0 and j >= 0:
			while i >= 0 and A[i] != B[j]:
				res += 1
				i -= 1
			i -= 1
			j -= 1
		return res


class Solution:

	def transfigure(self, A, B):
		if len(A) != len(B):
			return -1
		for d in set(A):
			if A.count(d) != B.count(d):
				return -1
		count = 0
		i = len(A) - 1
		j = len(B) - 1
		while i >= 0 and j >= 0:
			if A[i] == B[j]:
				i -= 1
				j -= 1
			else:
				i -= 1
				count += 1
		if count == len(A):
			return -1
		else:
			return count


class Solution:

	def transfigure(self, A, B):
		dic1 = {}
		for i in A:
			if i not in dic1:
				dic1[i] = 0
			dic1[i] += 1
		for i in B:
			if i not in dic1 or dic1[i] == 0:
				return -1
			else:
				dic1[i] -= 1
		for i in dic1:
			if dic1[i]:
				return -1
		i = len(A) - 1
		j = len(B) - 1
		res = 0
		while i >= 0 and j >= 0:
			while i >= 0 and A[i] != B[j]:
				i -= 1
				res += 1
			i -= 1
			j -= 1
		return res


from collections import deque

class Solution:

	def transfigure(self, A, B):
		M = {}
		if len(A) != len(B):
			return 0
		for i in range(len(A)):
			if A[i] not in M:
				M[A[i]] = 1
			else:
				M[A[i]] += 1
			if B[i] not in M:
				M[B[i]] = -1
			else:
				M[B[i]] -= 1
		for i in M:
			if M[i] > 0:
				return -1
		ans = 0
		i = len(A) - 1
		j = len(B) - 1
		while i >= 0:
			if A[i] == B[j]:
				i -= 1
				j -= 1
			else:
				ans += 1
				i -= 1
		return ans


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		if Counter(A) != Counter(B):
			return -1
		j = len(A) - 1
		add = 0
		for i in range(len(A))[::-1]:
			if A[i] != B[j]:
				add += 1
			else:
				j -= 1
		return add


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		if Counter(A) != Counter(B):
			return -1
		(a, b) = (len(A) - 1, len(B) - 1)
		trans = 0
		while a >= 0:
			if A[a] == B[b]:
				a -= 1
				b -= 1
			else:
				a -= 1
				trans += 1
		return trans


class Solution:

	def transfigure(self, A, B):
		if len(A) != len(B):
			return -1
		dic = {}
		for i in A:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for i in B:
			if i not in dic:
				return -1
			else:
				dic[i] -= 1
		for i in dic.keys():
			if dic[i] != 0:
				return -1
		count = 0
		j = len(A) - 1
		for i in range(len(A) - 1, -1, -1):
			if A[i] != B[j]:
				count += 1
			else:
				j -= 1
		return count


from collections import defaultdict
from time import time

class Solution:

	def transfigure(self, A, B):
		t0 = time()
		A = [*A]
		B = [*B]
		t1 = time()
		d = defaultdict(lambda : 0)
		d['A'] = 0
		t2 = time()
		while A and B:
			if A[-1] == B[-1]:
				B.pop()
				A.pop()
			else:
				d[A.pop()] += 1
		t3 = time()
		for item in B:
			d[item] -= 1
		t4 = time()
		return len(B) if set(d.values()) == set([0]) or not d else -1


class Solution:

	def transfigure(self, a, b):
		n1 = len(a)
		n2 = len(b)
		if n1 != n2:
			return -1
		freq = [0] * 256
		for cur in a:
			freq[ord(cur) - 97] += 1
		for cur in b:
			freq[ord(cur) - 97] -= 1
		for cur in freq:
			if cur != 0:
				return -1
		i = n1 - 1
		j = n2 - 1
		ans = 0
		while i >= 0:
			while i >= 0 and a[i] != b[j]:
				ans += 1
				i -= 1
			i -= 1
			j -= 1
		return ans


class Solution:

	def transfigure(self, A, B):
		m = len(A)
		n = len(B)
		if n != m:
			return -1
		count = {}
		keys = count.keys()
		for i in A:
			if i in keys:
				count[i] += 1
			else:
				count[i] = 1
		for i in B:
			if i in keys:
				count[i] -= 1
			else:
				count[i] = 1
		for i in keys:
			if count[i]:
				return -1
		res = 0
		i = n - 1
		j = n - 1
		while i >= 0:
			while i >= 0 and A[i] != B[j]:
				i -= 1
				res += 1
			if i >= 0:
				i -= 1
				j -= 1
		return res


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		if Counter(A) != Counter(B):
			return -1
		n = len(A)
		m = len(B)
		ans = 0
		for i in range(n - 1, -1, -1):
			if A[i] != B[m - 1]:
				ans += 1
			else:
				m -= 1
		return ans


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		if Counter(A) != Counter(B):
			return -1
		i = j = len(A) - 1
		while i >= 0:
			if A[i] == B[j]:
				j -= 1
			i -= 1
		return j + 1


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		from collections import Counter

class Solution:

	def transfigure(self, A, B):
		count = 0
		len1 = len(A)
		len2 = len(B)
		j = len1 - 1
		if A == B:
			return 0
		if len1 != len2:
			return -1
		if Counter(A) != Counter(B):
			return -1
		for i in range(len1 - 1, -1, -1):
			if A[i] != B[j]:
				count += 1
			else:
				j -= 1
		return count


class Solution:

	def transfigure(self, A, B):
		from collections import Counter
		if Counter(A) != Counter(B):
			return -1
		i = j = len(A) - 1
		while i >= 0:
			if A[i] == B[j]:
				j -= 1
			i -= 1
		return j + 1
		a_n = len(A)
		b_n = len(B)
		if a_n != b_n:
			return -1
		checking = [0] * 256
		for i in range(a_n):
			checking[ord(A[i])] += 1
			checking[ord(B[i])] -= 1
		for i in checking:
			if i != 0:
				return -1
		ans = 0
		(i, j) = (a_n - 1, b_n - 1)
		while i >= 0 and j >= 0:
			if A[i] != B[j]:
				ans += 1
				i -= 1
			else:
				j -= 1
				i -= 1
		return ans


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		if Counter(A) != Counter(B):
			return -1
		j = len(A) - 1
		add = 0
		for i in range(len(A))[::-1]:
			if A[i] != B[j]:
				add += 1
			else:
				j -= 1
		return add
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		A = line[0]
		B = line[1]
		obj = Solution()
		print(obj.transfigure(A, B))


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		(N, M) = (len(A), len(B))
		if N != M:
			return -1
		if Counter(A) != Counter(B):
			return -1
		i = j = N - 1
		fit = 0
		while i >= 0:
			if A[i] == B[j]:
				fit += 1
				j -= 1
			i -= 1
		return N - fit
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		A = line[0]
		B = line[1]
		obj = Solution()
		print(obj.transfigure(A, B))


from collections import Counter

class Solution:

	def transfigure(self, s1, s2):
		m = len(A)
		n = len(B)
		if n != m:
			return -1
		if Counter(s1) != Counter(s2):
			return -1
		res = 0
		j = n - 1
		for i in range(n - 1, -1, -1):
			if s1[i] != s2[j]:
				res += 1
			else:
				j -= 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		A = line[0]
		B = line[1]
		obj = Solution()
		print(obj.transfigure(A, B))


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		la = len(A)
		lb = len(B)
		if Counter(A) != Counter(B):
			return -1
		res = 0
		i = la - 1
		j = lb - 1
		while i >= 0:
			while i >= 0 and A[i] != B[j]:
				i -= 1
				res += 1
			if i >= 0:
				i -= 1
				j -= 1
		return res


from collections import Counter

class Solution:

	def transfigure(self, A, B):

		def find(A, B, i, j):
			search = B[j]
			while i >= 0:
				if A[i] == search:
					return i
				i -= 1
			return i
		if len(A) != len(B):
			return -1
		count_A = Counter(A)
		count_B = Counter(B)
		for (key, freq) in count_A.items():
			if key not in count_B or freq != count_B[key]:
				return -1
			else:
				count_B.pop(key)
		if len(count_B) != 0:
			return -1
		res = 0
		j = len(B) - 1
		i = len(A) - 1
		while i >= 0:
			if A[i] == B[j]:
				i -= 1
				j -= 1
			else:
				temp = find(A, B, i, j)
				res += i - temp
				i = temp
		return res


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		a = Counter(A)
		b = Counter(B)
		if a != b or len(A) != len(B):
			return -1
		else:
			i = len(A) - 1
			j = len(A) - 1
			c = 0
			while i >= 0:
				if A[i] == B[j]:
					j -= 1
				else:
					c += 1
				i -= 1
			return c


import collections

class Solution:

	def transfigure(self, A, B):
		d = {}
		if collections.Counter(A) != collections.Counter(B):
			return -1
		x = len(A)
		(cnt, j) = (0, x - 1)
		for i in range(x - 1, -1, -1):
			if A[i] == B[j]:
				j -= 1
			else:
				cnt += 1
		return cnt


from collections import Counter

class Solution:

	def transfigure(self, A, B):
		chars = {}
		CharsA = Counter(A)
		CharsB = Counter(B)
		if CharsA != CharsB:
			return -1
		if len(A) != len(B):
			return -1
		cnt = 0
		j = len(A) - 1
		i = len(A) - 1
		while i >= 0:
			if A[i] == B[j]:
				i -= 1
				j -= 1
			else:
				i -= 1
		return j + 1