Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input: d = {"ale", "apple", "monkey", "plea"}
       S = "abpcplea"
Output: "apple" 
Explanation: After deleting "b", "c"
"a" S became "apple" which is present
in d.
Example 2:
Input: d = {"a", "b", "c"}
       S = "abpcplea"
Output: "a"
Explanation: After deleting "b", "p"
"c", "p", "l", "e", "a" S became 
"a" which is present in d.
Your Task:  
You dont need to read input or print anything. Complete the function findLongestWord() which takes S and d as input parameter and returns the longest word.
Expected Time Complexity: O(n*x)
Expected Auxiliary Space: O(x)
Constraints:
1 ≤ n,x ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def findLongestWord (ob, S, d):

        # code here 



Solutions:
class Solution:

	def findLongestWord(ob, S, d):
		cur = ''
		for word in sorted(d):
			i = j = 0
			while i < len(S) and j < len(word):
				if word[j] == S[i]:
					j += 1
				i += 1
			if j == len(word) and len(word) > len(cur):
				cur = word
		return cur


class Solution:

	def findLongestWord(ob, S, d):
		result = ''
		length = 0
		for x in d:
			if length < len(x) and ob.isSubSequence(x, S):
				result = x
				length = len(x)
			elif length == len(x) and ob.isSubSequence(x, S) and (x < result):
				result = x
				length = len(x)
		return result

	def isSubSequence(ob, Str1, Str2):
		(m, n) = (len(Str1), len(Str2))
		(i, j) = (0, 0)
		while i < n and j < m:
			if Str1[j] == Str2[i]:
				j += 1
			i += 1
		return j == m


class Solution:

	def findLongestWord(ob, S, d):

		def isSubsequence(s1, s2):
			(m, n) = (len(s1), len(s2))
			(i, j) = (0, 0)
			while i < m and j < n:
				if s1[i] == s2[j]:
					i += 1
					j += 1
				else:
					j += 1
			return i >= m
		ans = ''
		for s1 in d:
			if isSubsequence(s1, S):
				if len(s1) > len(ans):
					ans = s1
				elif len(s1) == len(ans):
					ans = min(ans, s1)
		return ans


class Solution:

	def findLongestWord(ob, S, d):

		def check(i, j, n, m, w, S):
			if i == n:
				return True
			if j >= m:
				return False
			if S[j] == w[i]:
				return check(i + 1, j + 1, n, m, w, S)
			else:
				return check(i, j + 1, n, m, w, S)
			return False
		(m, s) = (0, '')
		p = len(S)
		for i in sorted(d):
			if check(0, 0, len(i), p, i, S):
				if len(i) > m:
					m = len(i)
					s = i
		return s


class Solution:

	def findLongestWord(ob, S, d):
		m = ''
		for i in d:
			j = k = 0
			while j < len(i) and k < len(S):
				if i[j] == S[k]:
					j += 1
				k += 1
			if j == len(i):
				if len(m) < len(i):
					m = i
				if len(m) == len(i):
					m = min(m, i)
		return m


class Solution:

	def isSubsequence(self, word, s):
		i = 0
		j = 0
		while i < len(s) and j < len(word):
			if s[i] == word[j]:
				j += 1
			i += 1
		return j == len(word)

	def findLongestWord(ob, S, d):
		d.sort()
		res = ''
		for word in d:
			if len(word) > len(res) and ob.isSubsequence(word, S):
				res = word
		return res


class Solution:

	def isSubSeq(self, str1, str2):
		l1 = len(str1)
		l2 = len(str2)
		(i, j) = (0, 0)
		while i < l1 and j < l2:
			if str1[i] == str2[j]:
				i += 1
			j += 1
		return i == l1

	def findLongestWord(ob, S, d):
		res = ''
		for word in d:
			l = len(res)
			if len(word) > l:
				if ob.isSubSeq(word, S):
					res = word
			elif len(word) == l and word < res and ob.isSubSeq(word, S):
				res = word
		return res


class Solution:

	def findLongestWord(ob, S, d):
		d = list(d)
		d.sort(key=lambda x: (-len(x), x))
		s = S
		length = 0
		word = ''
		for i in d:
			if length < len(i) and ob.isSub(s, i):
				word = i
				length = len(i)
		return word

	def isSub(self, st, word):
		stlen = 0
		wlen = 0
		while stlen < len(st) and wlen < len(word):
			if st[stlen] == word[wlen]:
				wlen += 1
			stlen += 1
		if wlen == len(word):
			return True
		else:
			return False


class Solution:

	def isSubsequence(self, a, b):
		(i, j) = (0, 0)
		while i < len(a) and j < len(b):
			if a[i] == b[j]:
				i += 1
			j += 1
		if i == len(a):
			return True
		return False

	def findLongestWord(ob, S, d):
		res = ''
		for i in d:
			if len(i) > len(res):
				if ob.isSubsequence(i, S):
					res = i
			elif len(i) == len(res) and i < res and ob.isSubsequence(i, S):
				res = i
		return res


class Solution:

	def findLongestWord(ob, S, d):

		def isSubsequence(s1, s2):
			i = 0
			j = 0
			while i < len(s1) and j < len(s2):
				if s1[i] == s2[j]:
					j += 1
				i += 1
			return True if j == len(s2) else False
		maxi = float('-inf')
		res = ''
		for word in d:
			if isSubsequence(S, word):
				if maxi < len(word):
					res = word
					maxi = len(word)
				elif maxi == len(word):
					res = min(res, word)
		return res


class Solution:

	def isSubSequence(self, str1, str2):
		m = len(str1)
		n = len(str2)
		j = 0
		i = 0
		while i < n and j < m:
			if str1[j] == str2[i]:
				j += 1
			i += 1
		if j == m:
			return True
		return False

	def findLongestWord(self, S, d):
		max_str = ''
		for word in d:
			if self.isSubSequence(word, S):
				if len(word) > len(max_str) or (len(word) == len(max_str) and word < max_str):
					max_str = word
		return max_str


from collections import defaultdict

class Solution:

	def findLongestWord(ob, s, d):
		d1 = defaultdict(int)
		d2 = defaultdict(list)
		ans = ''
		for i in range(len(s)):
			d1[s[i]] += 1
			d2[s[i]].append(i)
		d = list(d)
		ll = sorted(d, key=lambda x: (-len(x), x))
		for i in range(len(ll)):
			le = 0
			for j in ll[i]:
				if d1[j] != 0 and d1[j] >= ll[i].count(j):
					le += 1
					continue
				else:
					break
			if le == len(ll[i]):
				for j in range(len(d2[ll[i][0]])):
					m = 0
					for k in range(j, len(s)):
						if m < len(ll[i]) and s[k] == ll[i][m]:
							m += 1
						if m == len(ll[i]):
							break
					if m == len(ll[i]):
						return ll[i]
					else:
						continue
		return ans


class Solution:

	def findLongestWord(ob, S, d):

		def check(ele, s):
			i = 0
			j = 0
			while i < len(ele) and j < len(s):
				if ele[i] == s[j]:
					i += 1
					j += 1
				else:
					j += 1
			if i == len(ele):
				return True
			else:
				return False
		res = ''
		d.sort()
		for ele in d:
			if check(ele, S) and len(ele) > len(res):
				res = ele
		return res


class Solution:

	def check(self, w, S):
		i = 0
		for c in S:
			if c == w[i]:
				i += 1
				if i == len(w):
					return True
		return False

	def findLongestWord(self, S, d):
		s = ''
		for i in d:
			ans = self.check(i, S)
			if ans:
				if len(i) > len(s) or (len(i) == len(s) and i < s):
					s = i
		return s


class Solution:

	def findLongestWord(ob, S, d):
		results = []
		longest_word = ''
		for word in d:
			i = j = 0
			while i < len(word) and j < len(S):
				if word[i] == S[j]:
					i += 1
				j += 1
			if i == len(word):
				if len(word) > len(longest_word):
					longest_word = word
				elif len(word) == len(longest_word):
					longest_word = min(word, longest_word)
		return longest_word


class Solution:

	def findLongestWord(ob, S, d):
		max_length = -1
		max_str = ''
		for s in d:
			ind = -1
			temp = S
			char = 0
			while char < len(s):
				try:
					ind = temp.index(s[char])
				except:
					break
				temp = temp[ind + 1:]
				char += 1
			if char == len(s):
				if max_length < len(s):
					max_length = len(s)
					max_str = s
				if max_length == len(s):
					if s < max_str:
						max_str = s
		return max_str


class Solution:

	def findLongestWord(ob, S, d):
		strings = [[word, 0, False] for word in d]
		n = len(strings)
		for c in S:
			for i in range(n):
				(word, ind, isComp) = strings[i]
				if not isComp and word[ind] == c:
					strings[i][1] += 1
					if strings[i][1] == len(word):
						strings[i][2] = True
		res = ''
		for w in strings:
			if w[2]:
				if len(w[0]) > len(res):
					res = w[0]
				elif len(w[0]) == len(res) and w[0] < res:
					res = w[0]
		return res


class Solution:

	def findLongestWord(ob, S, d):
		c = ''
		for w in sorted(d):
			i = j = 0
			while i < len(S) and j < len(w):
				if w[j] == S[i]:
					j += 1
				i += 1
			if j == len(w) and len(w) > len(c):
				c = w
		return c


class Solution:

	def check(d, s, n, ans):
		i = 0
		j = 0
		while i < len(d) and j < len(s):
			if d[i] == s[j]:
				i += 1
			j += 1
			if i == len(d) and n < len(d):
				ans[0] = d

	def findLongestWord(ob, s, d):
		ans = ['']
		d.sort()
		n = 0
		for word in d:
			Solution.check(word, s, n, ans)
			n = len(ans[0])
		return ans[0]


class Solution:

	def findLongestWord(ob, s, d):
		d.sort(key=lambda x: (-len(x), x[0]))

		def isSubsequence(s, curString):
			(i, j) = (0, 0)
			while i < len(s) and j < len(curString):
				if s[i] == curString[j]:
					(i, j) = (i + 1, j + 1)
				else:
					i += 1
			return j == len(curString)
		for word in d:
			if isSubsequence(s, word):
				return word
		return ''


class Solution:

	def findLongestWord(self, S, d):
		self.res = ''

		def check(word, s):
			i = 0
			j = 0
			while i < len(word) and j < len(s):
				if word[i] == s[j]:
					i += 1
					j += 1
				else:
					j += 1
			if i == len(word) and len(self.res) < len(word):
				self.res = word
		d.sort()
		for w in d:
			check(w, S)
		return self.res


class Solution:

	def findLongestWord(ob, S, d):
		d = sorted(d)
		d = sorted(d, key=len, reverse=True)
		S = list(S)
		for word in d:
			if len(word) > len(S):
				continue
			newS = list(S[:])
			wordList = list(word)
			acceptable = True
			for i in range(0, len(newS)):
				if len(wordList) == 0:
					break
				elif len(newS) < len(wordList):
					acceptable = False
					break
				if newS[0] == wordList[0]:
					wordList.pop(0)
					newS.pop(0)
				elif wordList[0] not in newS:
					acceptable = False
					break
				else:
					newS.pop(0)
			if acceptable:
				return ''.join(word)
		return ''


class Solution:

	def findLongestWord(ob, S, d):
		for i in sorted(d, key=lambda x: (-len(x), x)):
			it = iter(S)
			if all((x in it for x in i)):
				return i
		return ''


class Solution:

	def findLongestWord(ob, S, d):
		d.sort()
		res = ''

		def check_subseq(s):
			nonlocal res
			i = 0
			for j in range(len(S)):
				if i < len(s) and S[j] == s[i]:
					i += 1
				j += 1
			if i == len(s) and i > len(res):
				res = s
		for s in d:
			check_subseq(s)
		return res


class Solution:

	def findLongestWord(ob, S, d):
		res = ''
		for m in sorted(d):
			i = 0
			j = 0
			while i < len(m) and j < len(S):
				if m[i] == S[j]:
					i += 1
				j += 1
			if i == len(m) and len(res) < len(m):
				res = m
		return res


from collections import Counter

class Solution:

	def findLongestWord(ob, S, d):
		longest = ''
		for w in d:
			if Solution.contains(S, w):
				if len(w) > len(longest):
					longest = w
				elif len(w) == len(longest):
					if w < longest:
						longest = w
		return longest

	def contains(x, y):
		n = len(x)
		m = len(y)
		(i, j) = (0, 0)
		while i < n and j < m:
			if x[i] == y[j]:
				i += 1
				j += 1
			else:
				i += 1
		return j == m


class Solution:

	def findLongestWord(ob, s, d):
		result = ''
		for word in d:
			i = 0
			for c in s:
				if i < len(word) and word[i] == c:
					i += 1
			if i == len(word) and len(word) >= len(result):
				if len(word) > len(result) or word < result:
					result = word
		return result


class Solution:

	def findLongestWord(ob, S, d):
		output = []
		for w in d:
			(a1, a2) = (len(S), len(w))
			(l1, l2) = (0, 0)
			while l1 < a1 and l2 < a2:
				if S[l1] == w[l2]:
					(l1, l2) = (l1 + 1, l2 + 1)
				else:
					l1 += 1
			if l2 == a2:
				output.append(w)
		output = sorted(output, key=len, reverse=True)
		l = len(output[0])
		for i in range(len(output) - 1, -1, -1):
			if len(output[i]) < l:
				output.pop()
			else:
				break
		output = sorted(output)
		return output[0]


class Solution:

	def subsequence(ob, str1, str2):
		m = len(str1)
		n = len(str2)
		i = 0
		j = 0
		while i < m and j < n:
			if str1[i] == str2[j]:
				j += 1
			i += 1
		return j == n

	def findLongestWord(ob, S, d):
		n = len(d)
		k = len(S)
		res = ''
		for i in d:
			if len(i) >= len(res) and Solution.subsequence(ob, S, i):
				if len(i) > len(res):
					res = i
				elif len(i) == len(res):
					if i < res:
						res = i
		return res


class Solution:

	def findLongestWord(ob, S, d):
		ans = ''
		for x in sorted(d):
			i = j = 0
			while i < len(S) and j < len(x):
				if x[j] == S[i]:
					j += 1
				i += 1
			if j == len(x) and len(x) > len(ans):
				ans = x
		return ans


class Solution:

	def findLongestWord(ob, S, d):

		def isSubsequence(S, n, a, k):
			i = 0
			j = 0
			while i < n and j < k:
				if S[i] == a[j]:
					j += 1
				i += 1
			if j == k:
				return True
			return False
		d.sort(key=lambda x: len(x), reverse=True)
		max_len = 0
		res = ''
		for x in d:
			if isSubsequence(S, len(S), x, len(x)):
				if max_len < len(x) or (max_len == len(x) and x < res):
					max_len = len(x)
					res = x
		if res:
			return res


class Solution:

	def findLongestWord(ob, S, d):
		d.sort(key=lambda x: (-len(x), x))

		def helper(sub, whole):
			(N, M) = (len(sub), len(whole))
			(i, j) = (0, 0)
			while i < N and j < M:
				if sub[i] == whole[j]:
					i += 1
				j += 1
			return i == N
		output = ''
		for w in d:
			if helper(w, S):
				return w
		return output


class Solution:

	def findLongestWord(ob, S, d):
		res = ''
		for word in d:
			i = 0
			j = 0
			while i < len(word) and j < len(S):
				if word[i] == S[j]:
					i += 1
					j += 1
				else:
					j += 1
			if i == len(word):
				if len(word) > len(res):
					res = word
				if len(word) == len(res):
					if word < res:
						res = word
		return res


class Solution:

	def findLongestWord(ob, S, d):
		arr = []
		for elem in d:
			count = 0
			i = 0
			j = 0
			while i < len(elem):
				if j < len(S):
					if elem[i] == S[j]:
						count += 1
						i += 1
						j += 1
					else:
						j += 1
				else:
					break
			if len(elem) == count:
				arr.append(elem)
		max_word = ''
		max_word_len = 0
		arr.sort()
		for elem in arr:
			if len(elem) > max_word_len:
				max_word = elem
				max_word_len = len(elem)
		return max_word


class Solution:

	def isSubsequence(str1, str2):
		m = len(str1)
		n = len(str2)
		i = 0
		j = 0
		while i < m and j < n:
			if str1[i] == str2[j]:
				i += 1
			j += 1
		if i == m:
			return True
		else:
			return False

	def findLongestWord(ob, S, d):
		longest = 0
		result = ''
		for word in d:
			if Solution.isSubsequence(word, S):
				if len(word) > longest:
					result = word
					longest = len(word)
				if len(word) == longest:
					result = word if word < result else result
		return result


class Solution:

	def findLongestWord(ob, s, d):

		def sub(st):
			l = len(st)
			i = 0
			j = 0
			while i < len(s) and j < len(st):
				if st[j] == s[i]:
					i += 1
					j += 1
				else:
					i += 1
			if j == len(st):
				return True
			return False
		cur = ''
		mx = 0
		for i in d:
			if sub(i):
				if len(i) > mx:
					mx = len(i)
					cur = i
				if len(i) == mx:
					cur = min(i, cur)
		return cur


class Solution:

	def f(self, S, i, w, j, dp):
		if j >= len(w):
			return ''
		if i >= len(S):
			return -1
		res = -1
		if S[i] == w[j]:
			res1 = self.f(S, i + 1, w, j + 1, dp)
			if res1 != -1:
				res = w[j] + res1
		else:
			res = self.f(S, i + 1, w, j, dp)
		return res

	def findLongestWord(ob, S, d):
		d.sort()
		d.sort(key=len, reverse=True)
		for i in range(len(d)):
			res = ob.f(S, 0, d[i], 0, {})
			if res != -1:
				return res


class Solution:

	def findLongestWord(ob, S, d):
		d.sort()
		(res, cnt) = ('', 0)
		Slen = len(S)

		def check(di, cnt, res):
			dlen = len(di)
			(i, j) = (0, 0)
			llocal = 0
			while i < dlen and j < Slen:
				if di[i] == S[j]:
					llocal += 1
					i += 1
					j += 1
				else:
					j += 1
				if i == dlen and llocal > cnt:
					cnt = llocal
					res = di
			return (cnt, res)
		for di in d:
			(cnt, res) = check(di, cnt, res)
		return res


def fun(a, b):
	i = 0
	for j in range(len(b)):
		if b[j] == a[i]:
			i += 1
			if i == len(a):
				return True
	return False

class Solution:

	def findLongestWord(ob, S, d):
		ans = ''
		temp = -1
		for i in d:
			if fun(i, S):
				if len(i) > temp:
					ans = i
					temp = len(i)
				if len(i) == temp:
					ans = min(i, ans)
		return ans


class Solution:

	def findLongestWord(ob, s, dict):
		n = len(s)
		dict.sort()
		dict.sort(key=len, reverse=True)
		ans = ''
		for d in dict:
			i = j = 0
			tmp = ''
			x = len(d)
			while i < n:
				if j < x and s[i] == d[j]:
					tmp += d[j]
					j += 1
				i += 1
			if tmp == d:
				ans = tmp
				break
		return ans


class Solution:

	def isstring(self, str1, str2):
		m = len(str1)
		n = len(str2)
		j = 0
		i = 0
		while i < n and j < m:
			if str1[j] == str2[i]:
				j += 1
			i += 1
		return j == m

	def findLongestWord(self, S, d):
		max_word = ''
		for i in d:
			if self.isstring(i, S):
				if len(i) > len(max_word) or (len(i) == len(max_word) and i < max_word):
					max_word = i
		return max_word


class Solution:

	def findLongestWord(ob, S, d):
		wrd = ''
		for word in d:
			k = 0
			for i in range(len(S)):
				if k == len(word):
					if len(word) > len(wrd):
						wrd = word
					elif len(word) == len(wrd) and word < wrd:
						wrd = word
					break
				elif S[i] == word[k]:
					k += 1
		return wrd


class Solution:

	def findLongestWord(ob, S, d):

		def h(w, t):
			c = 0
			ans = ''
			for i in w:
				for j in t[c:]:
					c += 1
					if j == i:
						ans += j
						break
			if ans == w:
				return True
			return False
		x = []
		for i in d:
			if h(i, S):
				x.append(i)
		if len(x) == 0:
			return -1
		l = 0
		for i in x:
			if len(i) > l:
				l = len(i)
		ans = []
		for i in x:
			if len(i) == l:
				ans.append(i)
		ans.sort()
		return ans[0]


class Solution:

	def findLongestWord(ob, S, d):
		t = ''
		for i in range(len(d)):
			j = 0
			count = 0
			for k in range(len(S)):
				if j < len(d[i]) and k < len(S) and (d[i][j] == S[k]):
					count += 1
					j += 1
					k += 1
					if count == len(d[i]):
						if len(t) < len(d[i]):
							t = d[i]
						elif len(t) == len(d[i]):
							t = min(t, d[i])
		return t


class Solution:

	def findLongestWord(ob, s, d):
		d.sort(key=lambda x: (-len(x), x))

		def solve(sub, whole):
			n = len(sub)
			m = len(whole)
			i = 0
			j = 0
			while i < n and j < m:
				if sub[i] == whole[j]:
					i += 1
				j += 1
			return i == n
		for w in d:
			if solve(w, s):
				return w
		return ''


class Solution:

	def word_exists(self, e, s):
		n = len(e)
		m = len(s)
		i = 0
		j = 0
		while i < n and j < m:
			if e[i] == s[j]:
				i += 1
			j += 1
		if i == n:
			return True
		else:
			return False

	def findLongestWord(self, S, d):
		new_d = {}
		max_len = 0
		for e in d:
			if self.word_exists(e, S):
				try:
					new_d[len(e)] = new_d[len(e)] + [e]
				except:
					new_d[len(e)] = [e]
				if len(e) >= max_len:
					max_len = len(e)
		new_l = sorted(new_d[max_len])
		if new_d:
			return new_l[0]
		else:
			return ''


class Solution:

	def findLongestWord(ob, S, d):

		def dfs(t, s):
			(i, j) = (0, 0)
			n = len(s)
			m = len(t)
			while i < n and j < m:
				if s[i] == t[j]:
					j += 1
				i += 1
				if j == m:
					return True
			return False
		ans = ''
		for i in d:
			if dfs(i, S):
				if len(ans) < len(i):
					ans = i
				elif len(ans) == len(i):
					ans = min(ans, i)
		return ans


class Solution:

	def findLongestWord(ob, s, d):

		def check(d, s):
			global res
			i = 0
			j = 0
			while i < len(d) and j < len(s):
				if d[i] == s[j]:
					i += 1
					j += 1
				else:
					j += 1
				if len(d) == i and len(res) < len(d):
					res = d
		global res
		res = ''
		d.sort()
		for i in d:
			check(i, s)
		return res


class Solution:

	def findLongestWord(ob, S, d):

		def issub(a, b):
			(i, j) = (0, 0)
			m = len(a)
			n = len(b)
			while i < m and j < n:
				if a[i] == b[j]:
					i += 1
					j += 1
				else:
					j += 1
			if i == m:
				return True
		output = ''
		for i in d:
			a = i
			b = S
			if issub(a, b):
				if len(a) >= len(output):
					if len(a) == len(output):
						if a < output:
							output = a
					else:
						output = a
		return output


class Solution:

	def findLongestWord(ob, S, d):

		def check(i, j, n, m, w, S):
			if i == n:
				return True
			if j >= m:
				return False
			if S[j] == w[i]:
				return check(i + 1, j + 1, n, m, w, S)
			else:
				return check(i, j + 1, n, m, w, S)
			return False
		(m, s) = (0, '')
		p = len(S)
		for i in sorted(d):
			if check(0, 0, len(i), p, i, S):
				if len(i) > m:
					m = len(i)
					s = i
		return s
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = input()
		n = int(n)
		d = input().split()
		for itr in range(n):
			d[itr] = d[itr]
		S = input()
		ob = Solution()
		print(ob.findLongestWord(S, d))


class Solution:

	def findLongestWord(ob, S, d):
		d.sort()
		res = ''
		for c in d:
			i = 0
			j = 0
			while i < len(c) and j < len(S):
				if c[i] == S[j]:
					i = i + 1
					j = j + 1
				else:
					j = j + 1
				if i == len(c) and len(res) < len(c):
					res = c
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = input()
		n = int(n)
		d = input().split()
		for itr in range(n):
			d[itr] = d[itr]
		S = input()
		ob = Solution()
		print(ob.findLongestWord(S, d))