Given an array of strings arr[]. You have to find the longest string which is lexicographically smallest and also all of its prefix strings are already present in the array.
 
Example 1:
Input: ab a abc abd
Output: abc
Explanation: We can see that length of the longest 
string is 3. And there are two string "abc" and "abd"
of length 3. But for string "abc" , all of its prefix
"a" "ab" "abc" are present in the array. So the
output is "abc".
Example 2:
Input: ab a aa abd abc abda abdd abde abdab
Output: abdab
Explanation: We can see that each string is fulfilling
the condition. For each string, all of its prefix 
are present in the array.And "abdab" is the longest
string among them. So the ouput is "abdab".
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function longestString() which takes the array arr[] as input parameter and returns the longest string which is also lexicographically smallest.And if there is no such string return empty string.
 
Expected Time Complexity: O(NlogN)
Expected Space Complexity: O(N)
 
Constraints:
1 <= length of arr[] <= 10^{3}
1 <= arr[i].length <=30

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3





class Solution():

    def longestString(self, arr, n):

        #your code goes here

Solutions:
class Solution:

	def longestString(self, arr, n):
		arr.sort()
		mp = {'': 0}
		result = ''
		for i in arr:
			if i[:-1] in mp:
				mp[i] = len(i)
				if mp[i] > len(result):
					result = i
		return result


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		c = ''
		for i in arr:
			pre = True
			for j in range(1, len(i)):
				if i[:j] not in arr:
					pre = False
					break
			if pre:
				if len(i) > len(c):
					c = i
		return c


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		candidate = ''
		for s in arr:
			prefixes_present = True
			for i in range(1, len(s)):
				if s[:i] not in arr:
					prefixes_present = False
					break
			if prefixes_present:
				if len(s) > len(candidate):
					candidate = s
		return candidate


class Solution:

	def longestString(self, arr, n):
		hash = set(arr)
		res = ''
		for i in range(len(arr)):
			have = True
			for j in range(len(arr[i])):
				if arr[i][0:j + 1] not in hash:
					have = False
					break
			if have:
				if len(res) < len(arr[i]):
					res = arr[i]
				elif len(res) == len(arr[i]):
					if arr[i] < res:
						res = arr[i]
		return res


class Solution:

	def longestString(self, arr, n):
		l = []
		for i in arr:
			a = ''
			k = 0
			for j in i:
				a = a + j
				if a in arr:
					pass
				else:
					k = 1
					break
			if k == 0:
				l += [i]
		if l == []:
			return ''
		l = sorted(l, key=len)
		m = l[-1]
		N = len(m)
		for i in sorted(l):
			if N == len(i):
				return i
		return ''


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		s = ''
		for i in arr:
			pf = True
			for j in range(1, len(i)):
				if i[:j] not in arr:
					pf = False
					break
			if pf:
				if len(i) > len(s):
					s = i
		return s


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		string_set = set(arr)
		max_len = 0
		ans = ''

		def isValid(str_curr):
			r = 1
			while r <= len(str_curr):
				if str_curr[:r] not in string_set:
					return False
				r += 1
			return True
		for string in arr:
			if isValid(string):
				if len(string) > max_len:
					max_len = len(string)
					ans = string
		return ans


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		map = {}
		l = []
		for string in arr:
			map[string] = 1
		for i in range(n - 1, -1, -1):
			s = arr[i]
			prefix = ''
			flag = True
			for j in range(len(s) - 1):
				prefix += s[j]
				if prefix not in map:
					flag = False
					break
			if flag == True:
				if len(l) == 0:
					l.append(s)
				elif len(s) >= len(l[0]):
					l.append(s)
			else:
				flag = False
		max_str = ''
		for i in l:
			if len(i) > len(max_str):
				max_str = i
			elif len(i) == len(max_str):
				if max_str > i:
					max_str = i
		return max_str


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		s = ''
		st = set()
		for i in arr:
			l = len(i)
			temp = ''
			f = 0
			for j in range(l - 1):
				temp += i[j]
				if temp not in st:
					f = 1
					break
			st.add(i)
			if f == 0:
				if len(i) > len(s):
					s = i
		return s


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		result = ''
		for s in arr:
			prev = True
			for i in range(1, len(s)):
				if s[:i] not in arr:
					prev = False
					break
			if prev:
				if len(s) > len(result):
					result = s
		return result


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		sub = ''
		for s in arr:
			pre = 1
			for i in range(1, len(s)):
				if s[:i] not in arr:
					pre = 0
					break
			if pre == 1:
				if len(s) > len(sub):
					sub = s
		return sub


class TrieNode:

	def __init__(self):
		self.children = [None for i in range(26)]
		self.isWord = False

class Trie:

	def __init__(self):
		self.Tree = TrieNode()

	def insert(self, s):
		cur = self.Tree
		prev = None
		for i in s:
			if cur.children[self.index(i)] is None:
				cur.children[self.index(i)] = TrieNode()
			prev = cur
			cur = cur.children[self.index(i)]
		cur.isWord = True

	def contains(self, s):
		cur = self.Tree
		cur.isWord = True
		prev = None
		for i in s:
			if cur.children[self.index(i)] is None or cur.isWord == False:
				return False
			prev = cur
			cur = cur.children[self.index(i)]
		return True

	def index(self, char):
		return ord(char) - ord('a')

class Solution:

	def longestString(self, arr, n):
		trie = Trie()
		for s in arr:
			trie.insert(s)
		ans = ''
		for s in arr:
			if trie.contains(s):
				if len(s) > len(ans):
					ans = s
				elif len(s) == len(ans):
					ans = min(ans, s)
		return ans


from collections import OrderedDict

class Solution:

	def longestString(self, arr, n):
		temp = OrderedDict()
		arr.sort(key=lambda ele: (len(ele), ele))
		for ele in arr:
			if len(ele) > 1:
				temp[ele] = temp.get(ele[:-1], False)
			else:
				temp[ele] = True
		l = 0
		sol = ''
		for i in temp:
			if temp[i] and len(i) > l:
				sol = i
				l = len(i)
		return sol


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		dict = {}
		for i in range(len(arr)):
			if len(arr[i]) == 1:
				dict[arr[i]] = True
			else:
				x = arr[i][:-1]
				if x in dict:
					dict[arr[i]] = dict[x]
		ans = ''
		for i in range(len(arr)):
			if arr[i] in dict and dict[arr[i]] and (len(arr[i]) > len(ans)):
				ans = arr[i]
		return ans


import math

class node:

	def __init__(self):
		self.d = dict()
		self.next = False

class Solution:

	def insert(self, name, root):
		temp = root
		for i in name:
			if temp.d.get(i) == None:
				temp.d[i] = node()
			temp = temp.d[i]
		temp.next = True

	def dfs(self, root):
		if root.next == False:
			return -10 ** 9
		count = 0
		for i in root.d.keys():
			a = 1 + self.dfs(root.d[i])
			count = max(count, a)
		return count

	def longestString(self, arr, n):
		root = node()
		for i in arr:
			self.insert(i, root)
		root.next = True
		a = self.dfs(root)
		d = dict()
		l = []
		for i in arr:
			d[i] = True
			if a == len(i):
				l.append(i)
		l1 = []
		for i in l:
			s = ''
			flag = 0
			for j in i:
				s = s + j
				if d.get(s) == None:
					flag = 1
					break
			if flag == 1:
				continue
			if flag == 0:
				l1.append(i)
		l1.sort()
		if len(l1) == 0:
			return ''
		return l1[0]


class Solution:

	def longestString(self, arr, n):
		s = set(arr)
		result = ''
		for list_index in range(len(arr)):
			prefix_present_in_array = True
			for string_index in range(len(arr[list_index])):
				if arr[list_index][:string_index + 1] not in s:
					prefix_present_in_array = False
					break
			if prefix_present_in_array:
				if len(result) < len(arr[list_index]):
					result = arr[list_index]
				elif len(result) == len(arr[list_index]):
					if arr[list_index] < result:
						result = arr[list_index]
		return result


class Solution:

	def longestString(self, arr, n):
		string = ''
		lengths = []
		updated_arr = []
		for each_str in arr:
			length = len(each_str)
			if length not in lengths:
				lengths.append(length)
		lengths.sort()
		lengths.reverse()
		min_length = min(lengths)
		for each_length in lengths:
			strings = []
			for each_str in arr:
				length = len(each_str)
				if length == each_length:
					strings.append(each_str)
			strings.sort()
			updated_arr.extend(strings)
		for each_str in updated_arr:
			found = 0
			for i in range(1, len(each_str)):
				if each_str[:i] not in updated_arr:
					found = 1
					break
			if found == 0:
				string = each_str
				break
		return string


class Solution:

	def longestString(self, arr, n):
		store = [[]]
		for item in arr:
			while len(store) < len(item):
				store.append([])
			store[len(item) - 1].append(item)
		items1 = ['']
		items2 = []
		for bucket in store:
			for item1 in items1:
				for item2 in bucket:
					if item1 == item2[:-1]:
						items2.append(item2)
			if not items2:
				return min(items1)
			items1 = items2.copy()
			items2 = []
		return min(items1)


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		max = ''
		dict = {}
		dict[''] = 1
		for i in range(n):
			if arr[i][:-1] in dict:
				dict[arr[i]] = 1
				if len(max) < len(arr[i]):
					max = arr[i]
		return max


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		d = set()
		for s in arr:
			d.add(s)
		ans = ''
		for s in arr:
			size = len(s)
			prefix = ''
			for ch in s:
				prefix += ch
				if prefix not in d:
					size = 0
					break
			if size > len(ans):
				ans = s
		return ans


class Solution:

	def longestString(self, arr, n):
		ans = ''
		arr.sort()
		for s in arr:
			le = len(s)
			ye = True
			for j in range(1, le):
				if s[:j] not in arr:
					ye = False
					break
			if ye:
				if len(s) > len(ans):
					ans = s
		return ans


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		check_value = set(arr)
		ans_string = ''
		ans = 0
		for string in arr:
			starting = True
			tmp_string = ''
			for ch in string:
				tmp_string += ch
				if tmp_string not in check_value:
					starting = False
					break
			if starting:
				if len(string) > ans:
					ans_string = string
					ans = len(string)
		return ans_string


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		ump = dict()
		ans = ''
		for j in range(n):
			if arr[j] in ump:
				ump[arr[j]] += 1
			else:
				ump[arr[j]] = 1
		for i in range(n):
			sz = len(arr[i])
			my_string = ''
			for s in arr[i]:
				my_string += s
				if my_string not in ump:
					sz = 0
					break
			if len(ans) < sz:
				ans = arr[i]
		return ans


class Solution:

	def longestString(self, arr, n):
		s = set(arr)
		f = True
		arr.sort(reverse=True)

		def allprefix(char):
			p = ''
			for i in char:
				p += i
				if p not in s:
					return False
			return True
		ans = ''
		for i in arr:
			if allprefix(i) and (f or len(i) >= l):
				ans = i
				l = len(ans)
				f = False
		return ans


class Solution:

	def longestString(self, arr, n):
		arr = sorted(arr)
		prefix = set()
		result = ''
		for string in arr:
			if all([string[:i] in prefix for i in range(1, len(string))]):
				if len(string) > len(result):
					result = string
			prefix.add(string)
		return result


class Solution:

	def longestString(self, arr, n):
		tmp = sorted(arr)
		tmp = sorted(tmp, key=len)
		returns = []
		stopping = 0
		for cand in tmp:
			if len(cand) == 1:
				returns.append(cand)
				continue
			ok = True
			for a in range(1, len(cand)):
				if cand[:a] in arr:
					pass
				else:
					ok = False
			if ok:
				returns.append(cand)
		if len(returns) == 0:
			return ''
		else:
			lens = [len(s) for s in returns]
			y = max(lens)
			filt = [s for s in returns if len(s) == y]
			if len(filt) != 0:
				return filt[0]
			else:
				return ''


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		m = ''
		s = set()
		for i in arr:
			k = len(i)
			t = ''
			f = 0
			for p in range(k - 1):
				t += i[p]
				if t not in s:
					f = 1
					break
			s.add(i)
			if f == 0:
				if len(i) > len(m):
					m = i
		return m


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		ans = ''
		for i in range(n):
			if arr[i] in ans:
				continue
			temp = arr[i]
			flag = True
			for j in range(1, len(temp)):
				if temp[:j] not in arr:
					flag = False
					break
			if flag and len(temp) > len(ans):
				ans = temp
		return ans


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		ans = ''
		mem = set()
		for v in arr:
			mem.add(v)
		for i in range(n):
			s = ''
			for sub in arr[i]:
				s += sub
				if s not in mem:
					s = ''
					break
			if len(s) > len(ans):
				ans = s
		return ans


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		longest_string = ''
		for string in arr:
			prefix = ''
			for char in string:
				prefix += char
				if prefix not in arr:
					break
			else:
				if len(string) > len(longest_string):
					longest_string = string
		return longest_string


class TrieNode:

	def __init__(self):
		self.childs = [None] * 26
		self.isEnd = False

class Trie:

	def __init__(self):
		self.root = self.getNewNode()

	def getNewNode(self):
		return TrieNode()

	def insert(self, value):
		curr = self.root
		for v in value:
			pos = ord(v) - ord('a')
			if not curr.childs[pos]:
				curr.childs[pos] = self.getNewNode()
			curr = curr.childs[pos]
		curr.isEnd = True

	def search(self, value):
		curr = self.root
		for v in value:
			pos = ord(v) - ord('a')
			if not curr.childs[pos].isEnd:
				return False
			curr = curr.childs[pos]
		return True

class Solution:

	def longestString(self, arr, n):
		t = Trie()
		for key in arr:
			t.insert(key)
		ans = ''
		for i in range(n):
			isPresent = t.search(arr[i])
			if isPresent:
				if len(arr[i]) > len(ans):
					ans = arr[i]
				elif len(arr[i]) == len(ans):
					if arr[i] < ans:
						ans = arr[i]
		return ans


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		st = set(arr)
		res = ''
		mn = -100000
		for str in arr:
			substr = ''
			count = 0
			for j in range(len(str)):
				substr += str[j]
				if substr in st:
					count += 1
			if count == len(str) and len(str) > mn:
				mn = len(str)
				res = str
		return res


from string import ascii_lowercase

class TrieNode:

	def __init__(self, char):
		self.char = char
		self.hasOcc = False
		self.children = {}

class Trie:

	def __init__(self):
		self.root = TrieNode('')

	def insert(self, string):
		curr = self.root
		for char in string:
			if char not in curr.children:
				curr.children[char] = TrieNode(char)
			curr = curr.children[char]
		curr.hasOcc = True

	def searchUtil(self, currNode, currString):
		if len(currString) > len(self.ans):
			self.ans = currString
		for char in ascii_lowercase:
			child = currNode.children.get(char, None)
			if char not in currNode.children:
				continue
			if not child.hasOcc:
				continue
			self.searchUtil(child, currString + char)

	def search(self):
		self.ans = ''
		self.searchUtil(self.root, '')
		return self.ans

class Solution:

	def longestString(self, arr, n):
		t = Trie()
		for string in arr:
			t.insert(string)
		return t.search()


class Solution:

	def longestString(self, arr, n):
		res = ''
		for num in arr:
			for i in range(1, len(num)):
				if num[:i] not in arr:
					break
			else:
				if len(num) > len(res):
					res = num
				elif len(num) == len(res):
					res = min(res, num)
		return res


class Solution:

	def longestString(self, arr, n):
		max_string = ''
		for alpha in arr:
			check_candidate = True
			for i in range(len(alpha)):
				if alpha[:i + 1] not in arr:
					check_candidate = False
					break
			if check_candidate and (len(alpha) > len(max_string) or (len(alpha) == len(max_string) and alpha < max_string)):
				max_string = alpha
		return max_string


def is_possible(prefs, word):
	for i in range(len(word)):
		pref = word[:i + 1]
		if pref in prefs:
			continue
		else:
			return False
	return True

class Solution:

	def longestString(self, a, n):
		cands = []
		prefs = {el: True for el in a}
		for word in a:
			if is_possible(prefs, word):
				cands.append([-len(word), word])
		return min(cands)[1] if cands else ''


ans = 0
ret = ''

class Trie:

	def __init__(self):
		self.isEnd = False
		self.children = [None] * 26

	def addString(root, str):
		if len(str) == 0:
			return 0
		ind = ord(str[0]) - ord('a')
		if root.children[ind] == None:
			newN = Trie()
			root.children[ind] = newN
		if len(str) == 1:
			root.children[ind].isEnd = True
			return
		Trie.addString(root.children[ind], str[1:])

	def findMax(root, currCount, strr):
		global ans
		global ret
		if root == None or root.isEnd == False:
			return
		if currCount > ans or (currCount == 0 and ret == ''):
			ans = currCount
			ret = strr
		if root.isEnd:
			for i in range(26):
				if root.children[i] != None:
					Trie.findMax(root.children[i], currCount + 1, strr + chr(ord('a') + i))

class Solution:

	def longestString(self, arr, n):
		global ans
		global ret
		ans = 0
		ret = ''
		root = Trie()
		for x in arr:
			Trie.addString(root, x)
		for i in range(26):
			Trie.findMax(root.children[i], 0, chr(ord('a') + i))
		return ret


class Solution:

	def longestString(self, arr, n):
		same_str = []
		maxl = 0
		pref = []
		for i in arr:
			pref.append(i)
			for j in range(1, len(i) + 1):
				if i[0:j] not in arr:
					pref.pop()
					break
		if len(pref) == 0:
			return ''
		else:
			for i in pref:
				if len(i) > maxl:
					maxl = len(i)
					same_str.clear()
					same_str.append(i)
				elif len(i) == maxl:
					same_str.append(i)
		x = same_str.pop()
		if len(same_str) == 0:
			return x
		else:
			for i in range(len(same_str)):
				if x > same_str[-1]:
					x = same_str.pop()
				else:
					del same_str[-1]
			return x


class Trie:

	def __init__(self, digit):
		self.digit = digit
		self.children = {}
		self.isend = False
		self.max_str = ''
		self.max_char = None

	def insert(self, w):
		if w[0] not in self.children:
			self.children[w[0]] = Trie(w[0])
		if len(w) == 1:
			self.children[w[0]].isend = True
		else:
			self.children[w[0]].insert(w[1:])

	def getmax(self):
		if not self.isend:
			return ''
		for c in sorted(self.children):
			s = self.children[c].getmax()
			if len(s) > len(self.max_str):
				self.max_str = s
		return self.digit + self.max_str

class Solution:

	def longestString(self, arr, n):
		t = Trie('')
		t.isend = True
		for s in arr:
			if len(s) == 0:
				continue
			t.insert(s)
		return t.getmax()


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		check = set(arr)
		ans = ''
		for s in arr:
			curr = ''
			count = 0
			for char in s:
				curr += char
				if curr not in check:
					break
				count += 1
			if count == len(s) and count > len(ans):
				ans = s
		return ans


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		temp = {'': 0}
		ans = ''
		for i in arr:
			if i[:-1] in temp:
				temp[i] = len(i)
				if temp[i] > len(ans):
					ans = i
		return ans


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndofWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def insert(self, word):
		curr = self.root
		for ele in word:
			index = ord(ele) - ord('a')
			if curr.children[index] is None:
				curr.children[index] = self.getNode()
			curr = curr.children[index]
		curr.isEndofWord = True

	def search(self, word):
		curr = self.root
		length = len(word)
		for ele in word:
			index = ord(ele) - ord('a')
			if curr.children[index] is None:
				return False
			curr = curr.children[index]
		return True

class Solution:

	def longestString(self, arr, n):
		hash = set(arr)
		res = ''
		for i in range(len(arr)):
			have = True
			for j in range(len(arr[i])):
				if arr[i][0:j + 1] not in hash:
					have = False
					break
			if have:
				if len(res) < len(arr[i]):
					res = arr[i]
				elif len(res) == len(arr[i]):
					if arr[i] < res:
						res = arr[i]
		return res


class Solution:

	def longestString(self, arr, n):
		arr = sorted(arr, key=lambda x: (len(x), x))
		s = set()
		for i in arr:
			s.add(i)
		res = ''

		def raji(i, s):
			for r in range(1, len(i)):
				k = i[0:r]
				if k not in s:
					return False
			return True
		for i in arr:
			if len(i) < len(res):
				continue
			elif raji(i, s):
				if len(i) > len(res):
					res = i
				elif i < res:
					res = i
		return res


from functools import cmp_to_key

def cmp(a, b):
	if len(a) != len(b):
		return len(a) - len(b)
	elif a < b:
		return 1
	elif a > b:
		return -1
	else:
		return 0

class Solution:

	def longestString(self, arr, n):
		s = set(arr)
		arr = sorted(arr, key=cmp_to_key(cmp), reverse=True)
		for st in arr:
			found = True
			for i in range(1, len(st)):
				if st[:i] not in s:
					found = False
					break
			if found:
				return st
		return ''


class Solution:

	def func(self, str, arr):
		m = ''
		for i in str:
			m = m + i
			if m not in arr:
				return False
		return True

	def longestString(self, arr, n):
		arr.sort()
		main = ''
		for i in arr:
			if self.func(i, arr):
				if len(main) > 0:
					if len(main) < len(i):
						main = i
				else:
					main = i
		return main


class TrieNode:

	def __init__(self):
		self.children = [None for _ in range(26)]
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def searchLevel(self, key):
		pCrawl = self.root
		length = len(key)
		l = 0
		for level in range(length):
			index = self._charToIndex(key[level])
			if pCrawl != self.root and (not pCrawl.isEndOfWord) or not pCrawl.children[index]:
				return 0
			pCrawl = pCrawl.children[index]
			l += 1
		return l if pCrawl.isEndOfWord else 0

class Solution:

	def longestString(self, arr, n):
		t = Trie()
		for i in arr:
			t.insert(i)
		m = 0
		s = ''
		for i in arr:
			l = t.searchLevel(i)
			if m < l:
				m = l
				s = i
			elif m == l and i < s:
				s = i
		return s


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		h_map = dict.fromkeys(arr, 0)
		for word in arr:
			h_map[word] += 1
		size = -float('inf')
		ans = ''
		for word in arr:
			c = 0
			n = len(word)
			temp = ''
			for j in range(n):
				temp += word[j]
				if temp in arr:
					c += 1
			if c == n and n > size:
				size = n
				ans = word
		return ans


class Solution:

	def longestString(self, arr, n):
		arr.sort(key=lambda x: len(x))
		seen = set()
		for s in arr:
			pre = s[:-1]
			if len(s) == 1:
				seen.add(s)
			if pre in seen:
				seen.add(s)
		mx = ''
		for s in seen:
			if len(s) == len(mx):
				mx = min(s, mx)
			elif len(s) > len(mx):
				mx = s
		return mx


def check(STR, val):
	c = False
	for j in range(1, len(val) + 1):
		if val[:j] in STR:
			c = True
		else:
			c = False
			break
	if c == False:
		return False
	else:
		return True

class Solution:

	def longestString(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		strings = sorted(arr, key=len)
		res = []
		for i in strings[::-1]:
			if len(res) != 0 and len(i) == len(res[0]):
				if i < res[0]:
					s = check(strings, i)
					if s == True:
						res[0] = i
			if len(res) == 0:
				s = check(strings, i)
				if s == True:
					res.append(i)
		if res != []:
			return res[0]
		else:
			return ''


class Solution:

	def longestString(self, arr, n):

		def SuffixesIn(seq):
			IsIn = 1
			for i in range(1, len(seq)):
				if seq[:i] not in HashMap:
					IsIn = 0
					break
			return IsIn
		LexOrder = {a: ind for (ind, a) in enumerate(sorted(arr))}
		MaxInd = -1
		HashMap = set()
		for seq in arr:
			HashMap.add(seq)
		for (ind, strin) in enumerate(arr):
			if SuffixesIn(strin):
				if MaxInd == -1:
					MaxInd = ind
				elif len(strin) > len(arr[MaxInd]):
					MaxInd = ind
				elif len(strin) == len(arr[MaxInd]) and LexOrder[strin] < LexOrder[arr[MaxInd]]:
					MaxInd = ind
		if MaxInd == -1:
			return ''
		return arr[MaxInd]


class node:

	def __init__(self):
		self.data = [None] * 26
		self.end = False

def solve(root, word):
	b = True
	n = len(word)
	count = 0
	for i in word:
		ind = ord(i) - ord('a')
		count += 1
		temp = root.data[ind]
		if temp == None and count < n:
			b = False
		if temp != None and temp.end == False:
			b = False
		if root.data[ind] == None:
			root.data[ind] = node()
		root = root.data[ind]
	root.end = True
	return b

class trie:

	def __init__(self):
		self.root = node()

	def insert(self, word):
		return solve(self.root, word)

def findLongestString(words):
	b = trie()
	out = ''
	temp = []
	for i in words:
		temp.append([len(i), i])
	temp.sort()
	for i in temp:
		c = b.insert(i[1])
		if c == True and len(out) < len(i[1]):
			out = i[1]
	return out

class Solution:

	def longestString(self, arr, n):
		return findLongestString(arr)


class Solution:

	def longestString(self, arr, n):
		d = sorted(arr, key=lambda x: (-len(x), x))
		i = 0
		maxi = 30
		x = 0
		while i <= maxi and x < n:
			if d[x][0:i + 1] not in d:
				x += 1
				i = 0
				continue
			i += 1
		if x >= n:
			return ''
		else:
			return d[x]


class Solution:

	def longestString(self, arr, n):
		a = sorted(arr, key=lambda x: (-len(x), x))
		i = 0
		max_i = 30
		q = 0
		while i <= max_i and q < n:
			if a[q][0:i + 1] not in a:
				q = q + 1
				i = 0
				continue
			i = i + 1
		if q >= n:
			return ' '
		else:
			return a[q]


from collections import defaultdict

class Solution:

	def longestString(self, arr, n):
		d = defaultdict(list)
		for i in arr:
			d[len(i)].append(i)
		r = list(d.keys())
		r.sort(reverse=True)
		for k in r:
			ct = 0
			c = d[k]
			c.sort()
			for i in c:
				for j in range(1, len(i)):
					if i[0:j] not in arr:
						break
				else:
					return i
					ct += 1
			if ct > 0:
				break
		if ct == 0:
			return ''


class Solution:

	def longestString(self, arr, n):
		arr.sort(key=len)
		valid = {''}
		for s in arr:
			if s[:-1] in valid:
				valid.add(s)
		return min(valid, key=lambda x: (-len(x), x))


class Solution:

	def longestString(self, arr, n):
		big = len(arr[0])
		f = 0
		str = []
		a = ''
		for i in arr:
			if len(i) > big:
				big = len(i)
		while big > 0:
			for i in arr:
				if len(i) == big:
					str.append(i)
			if len(str) == 0:
				big = big - 1
			else:
				str.sort()
				for j in str:
					ans = j
					f = 0
					for i in range(0, len(ans) - 1):
						if ans[0:i + 1] in arr:
							f = f + 1
					if f == len(ans) - 1:
						return ans
				big = big - 1
				str.clear()
		return a


class Solution:

	def longestString(self, arr, n):
		mx = list(map(len, arr))
		li = []
		while True:
			mx1 = max(mx)
			po = [x for x in arr if len(x) == mx1]
			for theWd in po:
				flag = True
				for i in range(1, len(theWd)):
					if theWd[0:i] not in arr:
						flag = False
						break
				if flag:
					li.append(theWd)
			if len(li) != 0:
				return min(li)
			mx = [x for x in mx if x != mx1]
			if len(mx) == 0:
				return ''


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		dict = {'': 0}
		res = ''
		for i in arr:
			if i[:-1] in dict:
				dict[i] = len(i)
				if len(i) > len(res):
					res = i
		return res


class Solution:

	def longestString(self, arr, n):
		arr.sort()
		sol = []
		for w in arr:
			if len(w) == 1:
				sol.append(w)
			elif w[:len(w) - 1] in sol:
				sol.append(w)
		ansWords = ['']
		for a in sol:
			if len(a) > len(ansWords[0]):
				ansWords = [a]
			elif len(a) == len(ansWords[0]):
				ansWords.append(a)
		return min(ansWords)


class TrieNode:

	def __init__(self):
		self.childNode = [None for _ in range(26)]
		self.end = ''
		self.wordCount = 0

	def insert_key(self, root, key):
		currentNode = root
		(i, l) = (0, len(key))
		f = 1
		while i < l:
			c = key[i]
			if currentNode.childNode[ord(c) - ord('a')] == None:
				newNode = TrieNode()
				currentNode.childNode[ord(c) - ord('a')] = newNode
			currentNode = currentNode.childNode[ord(c) - ord('a')]
			if currentNode.end != '$' and i != l - 1:
				f = 0
			i += 1
		currentNode.end = '$'
		currentNode.wordCount += 1
		return f

class Solution:

	def longestString(self, arr, n):
		temp = arr
		temp.sort()
		root = TrieNode()
		(max_len, max_idx) = (0, -1)
		for i in range(n):
			f = root.insert_key(root, temp[i])
			if f:
				if max_len < len(temp[i]):
					max_len = len(temp[i])
					max_idx = i
		if max_idx == -1:
			return ''
		return temp[max_idx]


from functools import cmp_to_key

def comparator(a, b):
	len_a = len(a)
	len_b = len(b)
	if len_a < len_b:
		return 1
	elif len_a > len_b:
		return -1
	elif a < b:
		return -1
	elif a > b:
		return 1
	else:
		return 0

class Solution:

	def longestString(self, arr, n):
		sorted_list = list(sorted(arr, key=cmp_to_key(comparator)))
		for i in range(n):
			included = True
			prefix = ''
			for j in range(len(sorted_list[i])):
				prefix = prefix + sorted_list[i][j]
				if prefix not in arr:
					included = False
					break
			if included:
				return sorted_list[i]
		return ''


from functools import cmp_to_key

def comparator(a, b):
	len_a = len(a)
	len_b = len(b)
	if len_a < len_b:
		return 1
	elif len_a > len_b:
		return -1
	elif a < b:
		return -1
	elif a > b:
		return 1
	else:
		return 0

class Solution:

	def longestString(self, arr, n):
		sorted_list = list(sorted(arr, key=cmp_to_key(comparator)))
		for i in range(n):
			included = True
			prefix = ''
			for j in range(len(sorted_list[i])):
				prefix = prefix + sorted_list[i][j]
				if prefix not in arr:
					included = False
					break
			if included:
				return sorted_list[i]
		return ''

	def longestString1(self, arr, n):
		prefix_included = []
		longest_len = 0
		for i in range(n):
			included = True
			prefix = ''
			current_len = len(arr[i])
			for j in range(current_len):
				prefix = prefix + arr[i][j]
				if prefix not in arr:
					included = False
					break
			if included:
				prefix_included.append(arr[i])
				if longest_len < current_len:
					longest_len = current_len
		if len(prefix_included) == 0:
			return ''
		longest_items = list(filter(lambda x: len(x) == longest_len, prefix_included))
		if len(longest_items) == 1:
			return longest_items[0]
		smallest = longest_items[0]
		for item in longest_items:
			if item < smallest:
				smallest = item
		return smallest


class Solution:

	def longestString(self, arr, n):
		s = set(arr)
		arr.sort(key=lambda x: (-len(x), x))
		i = 'huhnuvrfjyujntzwwncenvslbtpdr'
		for i in arr:
			for j in range(1, len(i)):
				if i[:j] not in s:
					break
			else:
				return i
		return ''