Given two strings S and T, find length of the shortest subsequence in S which is not a subsequence in T. If no such subsequence is possible, return -1. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. A string of length n has  different possible subsequences.
 
Example 1:
Input:
S = "babab"
T = "babba"
Output:
3
Explanation:
There are no subsequences of S with
length less than 3 which is not a
subsequence of T. "aab" is an example of
a subsequence of length 3 which isn't a
subsequence of T.
Example 2:
Input:
S = "babhi"
T = "babij"
Output:
1
Explanation:
"h" is a subsequence of S that is
not a subsequence of T.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function shortestUnSub() which takes two Strings S, and T as input and returns the shortest Uncommon Subsequence.
 
Expected Time Complexity: O(|S|^{2}*|T|)
Expected Auxiliary Space: O(|S|*|T|)
 
Constraints:
1 <= |S|, |T| <= 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def shortestUnSub(self, S, T):

        # code here 

Solutions:
class Solution:

	def __init__(self):
		self.indices = {}

	def shortestUnSub(self, S, T):
		m = len(S)
		n = len(T)
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(n + 1):
			dp[0][i] = 501
		for i in range(1, m + 1):
			dp[i][0] = 1
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				k = j - 1
				ch = S[i - 1]
				if ch == T[k]:
					self.indices[ch] = k
				elif ch in self.indices:
					k = self.indices[ch]
				else:
					while k >= 0:
						if T[k] == S[i - 1]:
							break
						k -= 1
					self.indices[ch] = k
				if k == -1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i - 1][k])
				ans = dp[i][j]
				if ans >= 501:
					ans = -1
		return ans


class Solution:

	def __init__(self):
		self.indices = {}

	def shortestUnSub(self, S, T):
		m = len(S)
		n = len(T)
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(n + 1):
			dp[0][i] = 501
		for i in range(1, m + 1):
			dp[i][0] = 1
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				k = j - 1
				ch = S[i - 1]
				if ch == T[k]:
					self.indices[ch] = k
				elif ch in self.indices:
					k = self.indices[ch]
				else:
					while k >= 0:
						if T[k] == S[i - 1]:
							break
						k -= 1
					self.indices[ch] = k
				if k == -1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i - 1][k])
				ans = dp[i][j]
				if ans >= 501:
					ans = -1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S, T) = map(str, input().split())
		ob = Solution()
		print(ob.shortestUnSub(S, T))


class Solution:

	def shortestUnSub(self, S, T):
		(m, n) = (len(S), len(T))
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(m + 1):
			dp[i][0] = 1
		for i in range(n + 1):
			dp[0][i] = float('inf')
		for i in range(m):
			for j in range(n):
				k = T[:j + 1].rfind(S[i])
				if k == -1:
					dp[i + 1][j + 1] = 1
				else:
					dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i][k] + 1)
		return -1 if dp[m][n] == float('inf') else dp[m][n]


class Solution:

	def __init__(self):
		self.index = {}

	def shortestUnSub(self, S, T):
		n = len(S)
		m = len(T)
		maxx = 501
		dp = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][0] = 1
		for j in range(m + 1):
			dp[0][j] = maxx
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				k = j - 1
				p = S[i - 1]
				if p == T[k]:
					self.index[p] = k
				elif p in self.index:
					k = self.index[p]
				else:
					while k >= 0:
						if S[i - 1] == T[k]:
							break
						k = k - 1
					self.index[p] = k
				if k == -1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i - 1][k])
				finalans = dp[i][j]
				if finalans >= maxx:
					finalans = -1
		return finalans


class Solution:

	def shortestUnSub(self, S, T):
		prev = [0 for _ in range(len(T) + 1)]
		for i in range(len(S), -1, -1):
			curr = [0 for _ in range(len(T) + 1)]
			for j in range(len(T), -1, -1):
				if i == len(S):
					curr[j] = float('inf')
					continue
				if j == len(T):
					curr[j] = 1
					continue
				k = T[j:].find(S[i])
				if k == -1:
					curr[j] = 1
					continue
				curr[j] = min(prev[j], 1 + prev[k + j + 1])
			prev = [k for k in curr]
		return -1 if curr[0] == float('inf') else curr[0]


INV = 10 ** 9 + 7

class Solution:

	def shortestUnSub(self, S, T):
		(NS, NT) = (len(S), len(T))
		dp = [[1] * (NT + 1) for _ in range(NS + 1)]
		for j in range(NT + 1):
			dp[NS][j] = INV
		startidx = {}
		for c in S:
			if c in startidx:
				continue
			startidx[c] = arr = [-1] * NT
			prev = -1
			for j in range(NT - 1, -1, -1):
				prev = j if T[j] == c else prev
				arr[j] = prev
		for i in range(NS - 1, -1, -1):
			arr = startidx.get(S[i], None)
			if arr is None:
				return 1
			for j in range(NT - 1, -1, -1):
				if S[i] == T[j]:
					dp[i][j] = min(1 + dp[i + 1][j + 1], dp[i + 1][j])
				else:
					dp[i][j] = 1 if arr[j] < 0 else min(dp[i + 1][j], 1 + dp[i + 1][arr[j] + 1])
		return -1 if dp[0][0] >= INV else dp[0][0]


import copy
MAX = 10000

class Solution:

	def shortestUnSub(self, S, T):
		rightmost = {}
		rightMost = [dict()] * len(T)
		for i in range(len(T)):
			if i:
				rightMost[i] = copy.deepcopy(rightMost[i - 1])
			rightMost[i][T[i]] = i

		def shortunseq(S, T):
			m = len(S)
			n = len(T)
			dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
			for i in range(m + 1):
				dp[i][0] = 1
			for i in range(n + 1):
				dp[0][i] = MAX
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					ch = S[i - 1]
					k = rightMost[j - 1].get(ch, -1)
					if k == -1:
						dp[i][j] = 1
					else:
						dp[i][j] = min(dp[i - 1][j], dp[i - 1][k] + 1)
			ans = dp[m][n]
			if ans >= MAX:
				ans = -1
			return ans
		return shortunseq(S, T)


from collections import defaultdict

class Solution:

	def shortestUnSub(self, text1, text2):
		(n, m) = (len(text1), len(text2))
		mapp = defaultdict(lambda : -1)
		dp = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(m + 1):
			dp[0][i] = 501
		for i in range(1, n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			mapp = defaultdict(lambda : -1)
			for j in range(1, m + 1):
				p = j - 1
				if text1[i - 1] == text2[p]:
					mapp[text1[i - 1]] = p
				p = mapp[text1[i - 1]]
				if p == -1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i - 1][p])
				mapp[text2[j - 1]] = j - 1
		return dp[-1][-1] if dp[-1][-1] != 501 else -1


class Solution:

	def shortestUnSub(self, S, T):
		dp = {0: 0}
		mem = dict()
		for length in range(1, len(S) + 1):
			dp2 = dict()
			for (s_start, t_start) in dp.items():
				visited = set()
				for i in range(s_start, len(S)):
					if S[i] not in visited:
						visited.add(S[i])
						if (S[i], t_start) not in mem:
							j = T.find(S[i], t_start)
							if j == -1:
								return length
							for pos in range(t_start, j + 1):
								if (S[i], pos) in mem:
									break
								mem[S[i], pos] = j
						dp2[i + 1] = max(dp2.get(i + 1, 0), mem[S[i], t_start] + 1)
			dp = dp2
		return -1


class Solution:

	def shortestUnSub(self, S, T):
		n = len(S)
		m = len(T)
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		MAX = float('inf')
		ind = dict()
		for i in range(m + 1):
			dp[0][i] = MAX
		for i in range(1, n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				k = j - 1
				ch = S[i - 1]
				if ch == T[k]:
					ind[ch] = k
				elif ch in ind:
					k = ind[ch]
				else:
					while k >= 0:
						if T[k] == ch:
							break
						k -= 1
					ind[ch] = k
				if k == -1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i - 1][k])
		ans = dp[n][m]
		if ans >= MAX:
			ans = -1
		return ans


class Solution:

	def __init__(self):
		self.indice = {}

	def shortestUnSub(self, S, T):
		dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
		for i in range(len(T) + 1):
			dp[0][i] = 501
		for i in range(1, len(S) + 1):
			dp[i][0] = 1
		for i in range(1, len(S) + 1):
			for j in range(1, len(T) + 1):
				k = j - 1
				char = S[i - 1]
				if char == T[k]:
					self.indice[char] = k
				elif char in self.indice:
					k = self.indice[char]
				else:
					while k >= 0:
						if T[k] == S[i - 1]:
							break
						k -= 1
					self.indice[char] = k
				if k == -1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i - 1][k])
				res = dp[i][j]
				if res >= 501:
					res = -1
		return res


class Solution:

	def shortestUnSub(self, S, T):
		best = [[-1] * (len(S) + 1) for _ in range(len(S))]
		bestbefore = [-1] * (len(S) + 1)
		for i in range(len(S)):
			tplaces = list(reversed([ind for (ind, c) in enumerate(T) if c == S[i]]))
			for l in range(1, i + 2):
				while tplaces and tplaces[-1] <= bestbefore[l - 1]:
					del tplaces[-1]
				best[i][l] = tplaces[-1] if tplaces else len(T)
			for l in range(1, i + 2):
				bestbefore[l] = max(bestbefore[l], best[i][l])
		minl = overflow = len(S) + 5
		for ilist in best:
			if len(T) in ilist:
				minl = min(minl, ilist.index(len(T)))
		return -1 if minl == overflow else minl


from math import inf

class Solution:

	def shortestUnSub(self, S, T):
		(n, m) = (len(S), len(T))
		dp = [[inf for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				k = T[:j].rfind(S[i - 1])
				if k == -1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i - 1][j], dp[i - 1][k] + 1)
		return dp[n][m] if dp[n][m] != inf else -1