Note: This POTD is a part of Geek Summer Carnival. Solve all POTD consecutively from 5th to 10th April and get a chance to win exclusive discount vouchers on our GfG courses.
Geek is at the geek summer carnival. He is given an array of N strings. To unlock exclusive course discounts he needs to find the longest common prefix among all strings present in the array. Can you help him ?
Example 1:
Input:
N = 4
ar[] = {geeksforgeeks, geeks, geek, geezer}
Output:
gee
Explanation: 
Longest common prefix in all the given string is gee. 
 
Example 2:
Input:
N = 3
ar[] = {apple, ape, april}
Output:
ap
Your Task:
You don't need to read input or print anything. Complete the function LCP() that takes integer n and ar[] as input parameters and return the LCP (in case there is no common prefix return -1). 
 
Expected time complexity: O(NlogN)
Expected space complexity: O(string length)
Constraints:
1 <= N <= 10^3
1 <= String Length <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def LCP(self,arr,n):

        #code here

Solutions:
class Solution:

	def LCP(self, arr, n):
		arr.sort()
		i = 0
		res = ''
		if arr[0][i] != arr[len(arr) - 1][i]:
			return -1
		while i < len(arr[0]) and arr[0][i] == arr[len(arr) - 1][i]:
			res += arr[0][i]
			i += 1
		return res


class Solution:

	def LCP(self, arr, n):
		string = ''
		for i in zip(*arr):
			if len(set(i)) == 1:
				string += i[0]
			elif len(string) != 0:
				return string
			else:
				return -1
		if len(string) != 0:
			return string
		else:
			return -1


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		s = arr[0]
		c = 0
		for i in range(len(s), -1, -1):
			p = s[:i]
			c = 0
			for j in arr:
				if p in j and j.index(p) == 0:
					c += 1
			if c == n and p != '':
				return p
		return -1


import os

class Solution:

	def LCP(self, arr, n):
		a = os.path.commonprefix(arr)
		if a == '':
			return -1
		return a


class TrieNode:

	def __init__(self):
		self.children = {}
		self.leaf = False

class Trie:

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

	def put(self, s):
		p = self.root
		for c in s:
			if not c in p.children:
				p.children[c] = TrieNode()
			p = p.children[c]

	def get(self, s):
		p = self.root
		for i in range(len(s)):
			if not s[i] in p.children:
				return s[:i]
			p = p.children[s[i]]
		return s

class Solution:

	def LCP(self, arr, n):
		root = Trie()
		root.put(arr[0])
		ans = arr[0]
		for i in range(1, n):
			s = root.get(arr[i])
			if len(s) < len(ans):
				ans = s
		return ans if len(ans) else '-1'


class Solution:

	def LCP(self, arr, n):
		a = sorted(arr)
		x = a[0]
		y = a[-1]
		b = min(len(x), len(y))
		s = ''
		k = 0
		while k < b:
			if x[k] == y[k]:
				s += x[k]
			else:
				break
			k += 1
		if len(s) == 0:
			return -1
		else:
			return s


class Solution:

	def LCP(self, a, n):
		a.sort()
		ans = ''
		i = 0
		while i < len(a[0]):
			if a[0][i] != a[-1][i]:
				break
			ans += a[0][i]
			i += 1
		if ans == '':
			return -1
		return ans


class Solution:

	def LCP(self, arr, n):
		arr = sorted(arr)
		sm = arr[0]
		lg = arr[-1]
		i = 0
		j = 0
		sb = []
		while i < len(sm) and j < len(lg):
			if sm[i] != lg[j]:
				break
			sb.append(sm[i])
			i += 1
			j += 1
		if len(sb) == 0:
			return -1
		else:
			return ''.join(sb)


class Solution:

	def LCP(self, arr, n):
		temp = arr[0]
		if n == 1:
			return temp
		for i in range(1, n):
			a = 0
			b = 0
			ans = ''
			while a < len(temp) and b < len(arr[i]) and (temp[a] == arr[i][b]):
				ans += temp[a]
				a += 1
				b += 1
			temp = ans
		return ans if ans else -1


class Solution:

	def LCP(self, arr, n):
		if not arr:
			return ''
		prefix = arr[0]
		for i in range(1, len(arr)):
			while not arr[i].startswith(prefix):
				prefix = prefix[:-1]
				if not prefix:
					return -1
		return prefix


class Solution:

	def LCP(self, arr, n):
		output = arr[0]
		for item in arr[1:]:
			n = min(len(output), len(item))
			output = output[:n]
			item = item[:n]
			for i in range(n):
				if item[i] != output[i]:
					output = output[:i]
					break
		return output if output else -1


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		firs = arr[0]
		last = arr[-1]
		out = ''
		for i in range(min(len(firs), len(last))):
			if firs[i] == last[i]:
				out += firs[i]
			else:
				break
		if len(out) >= 1:
			return out
		else:
			return -1


class Solution:

	def LCP(self, arr, n):
		arr.sort(key=lambda x: len(x))
		com = arr[0]
		for i in range(1, n):
			curr = ''
			for j in range(len(com)):
				if com[j] != arr[i][j]:
					break
			else:
				j += 1
			com = com[:j]
		if com == '':
			return -1
		return com


class Solution:

	def LCP(self, a, n):
		mini = 101
		for i in a:
			mini = min(mini, len(i))
		s = ''
		for i in range(mini):
			r = a[0][i]
			j = 0
			while j < n:
				if a[j][i] != r:
					break
				j += 1
			if j != n:
				break
			else:
				s += r
		if s == '':
			return -1
		else:
			return s


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		if len(arr[0]) > 1:
			k = 0
			while k < len(arr[0]):
				l = arr[0][k]
				for i in range(n):
					if arr[i][k] != l:
						if k == 0:
							return -1
						return arr[0][:k]
						break
				k += 1
			else:
				return arr[0]
		if len(arr[0]) == 1:
			l = arr[0]
			for i in range(n):
				if arr[i][0] != l:
					return -1
			return l


class Solution:

	def LCP(self, arr, n):
		d = len(min(arr))
		s = []
		for i in range(d):
			if all((arr[0][i] == j[i] for j in arr)):
				s.append(arr[0][i])
			else:
				break
		if ''.join(s) != '':
			return ''.join(s)
		else:
			return -1


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		fst = arr[0]
		lcp = len(fst)
		for e in arr:
			i = 0
			while fst[i] == e[i]:
				i += 1
				if i >= lcp or i >= len(e):
					break
			if i < lcp:
				lcp = i
		if lcp == 0:
			return -1
		return fst[:lcp]


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		length = len(arr[0])
		cur = 0
		state = False
		path = ''
		while cur < length:
			for i in range(n - 1):
				if arr[i][cur] != arr[i + 1][cur]:
					state = True
					break
			if not state:
				path += arr[0][cur]
			if state:
				break
			cur += 1
		if path == '':
			return -1
		return path


class Solution:

	def LCP(self, arr, n):
		sortedArr = sorted(arr)
		shortest = sortedArr[0]
		for i in range(len(shortest)):
			prefix = shortest[:i + 1]
			for s in sortedArr:
				if not s.startswith(prefix):
					if i == 0:
						return -1
					else:
						return shortest[:i]
		return shortest


class Solution:

	def LCP(self, a, n):
		size = len(a)
		if size == 0:
			return ''
		if size == 1:
			return a[0]
		a.sort()
		end = min(len(a[0]), len(a[size - 1]))
		i = 0
		while i < end and a[0][i] == a[size - 1][i]:
			i += 1
		pre = a[0][0:i]
		if pre:
			return pre
		else:
			return -1


class Solution:

	def LCP(self, arr, n):
		if n == 0:
			return 0
		if n == 1:
			return arr[0]
		arr.sort()
		end = min(len(arr[0]), len(arr[1]))
		i = 0
		s = ''
		while i < end and arr[0][i] == arr[n - 1][i]:
			s = s + arr[0][i]
			i = i + 1
		if len(s) == 0:
			return -1
		return s


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		t = ''
		c = 0
		for i in arr[0]:
			m = t
			t += i
			c += 1
			for i in range(1, n):
				if t != arr[i][:c]:
					if len(m) == 0:
						return '-1'
					return m
		return t


class Solution:

	def LCP(self, arr, n):

		def smalli(arr):
			mine = len(arr[0])
			for i in range(1, len(arr)):
				mine = min(mine, len(arr[i]))
			return mine

		def lcp(arr):
			a_i = smalli(arr)
			res = ''
			for i in range(a_i):
				t = arr[0][i]
				for j in range(1, len(arr)):
					if t != arr[j][i]:
						return res if len(res) != 0 else -1
				res += t
			return res if len(res) != 0 else -1
		return lcp(arr)


class Solution:

	def LCP(self, arr, n):
		l = sorted(arr, key=len)
		k = 0
		x = []
		c = 0
		for i in range(len(l[0])):
			for j in range(1, n):
				if l[0][i] == l[j][k]:
					c = 0
				else:
					c = 1
					break
			k = k + 1
			if c == 1:
				break
			if c == 0:
				x.append(l[0][i])
		y = ''
		for i in x:
			y = y + i
		if y == '':
			return -1
		else:
			return y
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		arr = [x for x in input().split()]
		obj = Solution()
		print(obj.LCP(arr, n))


class Solution:

	def LCP(self, arr, n):
		x = ''
		arr.sort()
		for i in range(min(len(arr[0]), len(arr[-1]))):
			if arr[0][i] == arr[-1][i]:
				x = x + arr[0][i]
			else:
				break
		if len(x) == 0:
			return -1
		return x
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		arr = [x for x in input().split()]
		obj = Solution()
		print(obj.LCP(arr, n))


class Solution:

	def LCP(self, arr, n):
		res = ''
		for i in range(len(arr[0])):
			for s in arr:
				if i == len(s) or s[i] != arr[0][i]:
					if res == '':
						res = -1
					return res
			res += arr[0][i]
		if res == '':
			res = -1
		return res


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		x = ''
		for i in range(min(len(arr[0]), len(arr[-1]))):
			if arr[0][i] == arr[-1][i]:
				x += arr[0][i]
			else:
				break
		if len(x) == 0:
			return '-1'
		return x


class Solution:

	def LCP(self, arr, n):
		cnt = len(min(arr))
		cnt += 1
		i = 1
		while i < n:
			if cnt == 0:
				return -1
			if arr[i][:cnt] == arr[i - 1][:cnt]:
				i += 1
			else:
				cnt -= 1
		return arr[0][:cnt]


class Solution:

	def LCP(self, a, n):
		a.sort()
		t = ''
		for i in range(len(a[0])):
			if a[0][i] == a[-1][i]:
				t += a[0][i]
			else:
				break
		return t if t else -1


class Solution:

	def LCP(self, arr, n):
		min1 = 1000
		for i in range(n):
			if min1 > len(arr[i]):
				min1 = len(arr[i])
		if n == 1:
			return ''.join(arr)
		i = 0
		output = ''
		while i < min1:
			t = arr[0][i]
			c = 0
			for j in range(1, n):
				if t == arr[j][i]:
					c += 1
					if c == n - 1:
						output += arr[j][i]
			i += 1
		if len(output) == 0:
			return -1
		return output


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		s = arr[0]
		c = 0
		for x in range(len(s), -1, -1):
			p = s[:x]
			c = 0
			for y in arr:
				if p in y and y.index(p) == 0:
					c += 1
			if c == n and p != '':
				return p
		return -1


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		s = arr[0]
		c = 0
		for i in range(len(s), -1, -1):
			p = s[:i]
			c = 0
			for j in arr:
				if p in j and j.index(p) == 0:
					c += 1
			if c == n and p != '':
				return p
		return -1
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		arr = [x for x in input().split()]
		obj = Solution()
		print(obj.LCP(arr, n))


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		a = arr[0]
		b = arr[n - 1]
		c = 0
		for i in range(min(len(a), len(b))):
			if a[i] == b[i]:
				c += 1
			else:
				break
		if c == 0:
			return -1
		return arr[0][:c]


class Solution:

	def LCP(self, arr, n):
		ans = len(arr[0])
		for idx in range(1, n):
			i = 0
			j = 0
			while i < len(arr[idx - 1]) and j < len(arr[idx]):
				if arr[idx - 1][i] == arr[idx][j]:
					i += 1
					j += 1
				else:
					break
			ans = min(ans, i, j)
			if ans == 0:
				return -1
		return arr[0][:ans]


class Solution:

	def LCP(self, arr, n):
		arr.sort(key=len)
		if arr == None or len(arr) == 0:
			return -1
		elif arr[0] == None or len(arr[0]) == 0:
			return -1
		elif len(arr) == 1:
			return arr[0]
		count = len(arr[0])
		while count > 0:
			if all((word.startswith(arr[0][0:count]) for word in arr[1:])):
				return arr[0][0:count]
			else:
				count -= 1
		return -1


class Solution:

	def LCP(self, arr, n):
		pref = ''
		minl = float('inf')
		for i in range(n):
			if len(arr[i]) < minl:
				minl = len(arr[i])
				pref = arr[i]
		for i in range(n):
			for j in range(minl):
				if pref[j] != arr[i][j]:
					minl = j
					pref = pref[:j]
					break
		if len(pref) == 0:
			return -1
		return pref


class Solution:

	def LCP(self, arr, n):
		ans = ''
		x = []
		for i in arr:
			x.append(len(i))
		y = min(x)
		for i in range(y):
			z = []
			for j in arr:
				z.append(j[i])
			if len(set(z)) == 1:
				ans += z[0]
		if ans:
			return ans
		else:
			return -1


class Solution:

	def LCP(self, arr, n):
		arr = sorted(arr, key=len)
		s = arr[0]
		p = ''
		for i in range(len(s)):
			c = 0
			for j in arr:
				if j[i] != s[i]:
					c = 1
			if c == 0:
				p = p + s[i]
		if p == '':
			return -1
		else:
			return p


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		for i in range(len(arr[0]), -1, -1):
			fl = 0
			for j in range(len(arr)):
				if arr[0][:i] in arr[j] and arr[j].index(arr[0][:i]) == 0:
					fl = fl + 1
			if fl == len(arr) and arr[0][:i] != '':
				return arr[0][:i]
		return -1


class Solution:

	def LCP(self, arr, n):
		smallest = arr[0]
		for i in arr:
			if len(i) < len(smallest):
				smallest = i
		prefix = ''
		longest_prefix = ''
		for i in range(len(smallest)):
			prefix += smallest[i]
			flag = 1
			for string in arr:
				if string[0:i + 1] != prefix:
					flag = 0
			if flag == 1:
				longest_prefix = prefix
		if longest_prefix:
			return longest_prefix
		else:
			return -1


class Solution:

	def LCP(self, arr, n):
		ans = ''
		a = list(zip(*arr))
		for i in range(len(a)):
			if len(set(a[i])) == 1:
				ans += a[i][0]
			else:
				break
		if len(ans) > 0:
			return ans
		return -1


class Solution:

	def LCP(self, arr, n):
		mini = 9999
		smin = ''
		for i in range(n):
			if len(arr[i]) < mini:
				smin = arr[i]
				mini = len(arr[i])
				k = i
		arr.remove(smin)
		i = 0
		s = ''
		n1 = len(arr)
		while i < mini:
			c = 0
			for j in range(n1):
				if smin[i] == arr[j][i]:
					c += 1
				else:
					if s == '':
						return '-1'
					return s
			if c == n1:
				s += smin[i]
			i += 1
		return smin


class Solution:

	def LCP(self, arr, n):
		strs = arr
		for i in range(0, len(strs)):
			for j in range(0, len(strs) - i - 1):
				if len(strs[j]) > len(strs[j + 1]):
					temp = strs[j]
					strs[j] = strs[j + 1]
					strs[j + 1] = temp
		s = ''
		d = str(strs[0])
		flag = 0
		for i in range(0, len(d)):
			counter = 0
			for j in range(0, len(strs)):
				f = str(strs[j])
				if d[i] == f[i]:
					counter = counter + 1
				else:
					flag = 1
					break
			if flag == 1:
				break
			if counter == len(strs):
				s = s + d[i]
		if len(s) == 0:
			return '-1'
		return s


class Solution:

	def LCP(self, arr, n):
		prefix = list(arr[0])
		for s in arr:
			if not prefix:
				return -1
			res = []
			i = 0
			for char in prefix:
				if i < len(s):
					if s[i] == char:
						res.append(char)
						i += 1
					else:
						break
			prefix = res
		return ''.join(prefix)


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		x = arr[0]
		y = arr[-1]
		m = len(x)
		i = 0
		s = ''
		while i < m:
			if x[i] != y[i]:
				break
			s += x[i]
			i += 1
		if len(s) == 0:
			return -1
		else:
			return s


def solve(pfx, str1):
	res = ''
	n1 = len(pfx)
	n2 = len(str1)
	i = 0
	j = 0
	while i <= n1 - 1 and j <= n2 - 1:
		if pfx[i] != str1[j]:
			break
		res += pfx[i]
		i += 1
		j += 1
	return res

class Solution:

	def LCP(self, arr, n):
		prefix = arr[0]
		for i in range(1, len(arr)):
			prefix = solve(prefix, arr[i])
		if len(prefix) == 0:
			return -1
		return prefix


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		st = arr[0]
		en = arr[-1]
		if len(st) > len(en):
			n = len(en)
		else:
			n = len(st)
		i = 0
		ans = ''
		while i < n:
			if st[i] == en[i]:
				ans += st[i]
				i += 1
			else:
				break
		if len(ans) == 0:
			return -1
		return ans


class Solution:

	def LCP(self, arr, n):
		ans = ''
		fail = False
		for i in range(100):
			c = 0
			for j in arr:
				if i >= len(j):
					fail = True
					break
				if j[i] == arr[0][i]:
					c += 1
			if fail:
				break
			if c == n:
				ans += arr[0][i]
			else:
				break
		if ans:
			return ans
		return -1


class Solution:

	def LCP(self, arr, n):
		a = min(arr, key=len)
		arr.remove(a)
		res = ''
		for i in range(len(a)):
			x = 0
			b = a[i]
			for j in arr:
				if j[i] == b:
					x += 1
			if x == len(arr):
				res += b
		return res if res != '' else -1


class Solution:

	def LCP(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		arr.sort(key=len)
		s = arr[0]
		i = 0

		def compare(s, i, arr):
			if not arr[i].startswith(s):
				return False
			elif i == len(arr) - 1:
				return True
			return compare(s, i + 1, arr)
		while len(s) >= 1:
			res = compare(s, 1, arr)
			if res == True and len(s) >= 1:
				return s
			s = s[:-1]
		return '-1'


class Solution:

	def LCP(self, arr, n):
		arr.sort(key=lambda x: len(x))
		w = 1
		while w <= len(arr[0]):
			s = arr[0][0:w]
			for j in range(1, n):
				if arr[j][0:w] != s:
					if w == 1:
						return -1
					return arr[0][0:w - 1]
			w += 1
		return s


class Solution:

	def LCP(self, strs, n):
		k = min(arr, key=len)
		(lo, hi) = (0, len(k) + 1)
		while lo < hi:
			mi = lo + (hi - lo) // 2
			if self.ok(arr, k[:mi]):
				hi = mi
			else:
				lo = mi + 1
		return k[:lo - 1] if lo > 1 else -1

	def ok(self, arr, s):
		for e in arr:
			if not e.startswith(s):
				return True
		return False


class Solution:

	def __init__(self):
		self.req = ''

	def LCP(self, arr, n):
		left = 1
		right = len(arr[0])
		while left <= right:
			mid = (left + right) // 2
			if self.CompareStr(arr, mid):
				left = mid + 1
			else:
				right = mid - 1
		mid = (left + right) // 2
		return -1 if not arr[0][:mid] else arr[0][:mid]

	def CompareStr(self, arr, mid):
		for i in range(len(arr)):
			if arr[i].find(arr[0][:mid]) != 0:
				return False
		return True


class Solution:

	def LCP(self, arr, n):
		left = 1
		right = len(arr[0])
		while left <= right:
			mid = (left + right) // 2
			if self.binarySearch(arr, mid):
				left = mid + 1
			else:
				right = mid - 1
		return -1 if not arr[0][:(left + right) // 2] else arr[0][:(left + right) // 2]

	def binarySearch(self, arr, middle):
		for i in range(len(arr)):
			if arr[i].find(arr[0][0:middle]) != 0:
				return False
		return True


class Solution:

	def LCP(self, arr, n):
		c = 0
		s = ''
		list1 = arr.copy()
		if n == 0:
			return -1
		if n == 1:
			return arr[0]
		l1 = len(list1)
		list1.sort()
		x = list1.pop(0)
		y = list1.pop(l1 - 2)
		for i in range(len(x)):
			if x[i] == y[i]:
				s += x[i]
			else:
				break
		if len(s) == 0:
			return -1
		else:
			return s


class Solution:

	def LCP(self, arr, n):
		temp = []
		for i in arr:
			temp.append([len(i), i])
		temp.sort()
		ans = ''
		pos = temp[0][1]
		for x in range(len(pos)):
			for i in range(1, n):
				if pos[x] != temp[i][1][x]:
					if ans == '':
						return -1
					return ans
			ans += pos[x]
		if ans == '':
			return -1
		return ans


class Solution:

	def LCP(self, arr, n):
		if n == 1:
			return arr[0]
		for i in arr:
			if len(i) == 0 or len(i) > 50:
				return -1
		lcp = ''
		arr2 = sorted(arr, key=len)
		inlcp = 'false'
		for i in arr2[0]:
			inlcp = 'false'
			for j in arr2:
				if i in j:
					inlcp = 'true'
				else:
					inlcp = 'false'
					break
			if inlcp == 'true':
				lcp = lcp + i
		if lcp == '' or not 1 <= n <= 1000:
			return -1
		else:
			return lcp


class Solution:

	def LCP(self, arr, n):
		min_str = min(arr, key=len)
		ans_str = -1
		for i in range(len(min_str)):
			cur_str = min_str[:i + 1]
			for j in arr:
				if cur_str != j[:i + 1]:
					return ans_str
			else:
				ans_str = cur_str
		return ans_str


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		l = min(len(arr[0]), len(arr[-1]))
		i = 0
		while i < l and arr[0][i] == arr[-1][i]:
			i += 1
		return arr[0][:i] if i != 0 else -1


class Solution:

	def LCP(self, arr, n):
		lenth = len(arr[0])
		for i in range(0, n - 1):
			count = 0
			for j in range(0, len(arr[i])):
				try:
					if arr[i][j] == arr[i + 1][j]:
						count += 1
					else:
						break
				except IndexError:
					pass
			if count < lenth:
				lenth = count
		if lenth == 0:
			return -1
		else:
			return arr[0][:lenth]


class Solution:

	def LCP(self, arr, n):
		arr.sort()
		if arr[0] == arr[-1]:
			return arr[0]
		for (i, char) in enumerate(arr[-1]):
			try:
				if arr[0][i] != char:
					break
			except IndexError:
				break
		if i == 0:
			return -1
		return arr[0][:i]


class Solution:

	def LCP(self, arr, n):
		string_str = min(arr, key=len)
		ans = str()
		for i in range(len(string_str)):
			cur_ref_string = string_str[:i + 1]
			for j in arr:
				if cur_ref_string != j[:i + 1]:
					return ans if len(ans) else -1
			else:
				ans = cur_ref_string
		return ans if len(ans) else -1


class Solution:

	def LCP(self, arr, n):
		small_element = arr[0]
		for ele in arr:
			if small_element < ele:
				small_element = ele
		l = len(small_element)
		while l > 0:
			count = 0
			for i in arr:
				if small_element == i[:l]:
					count += 1
			if count == len(arr):
				return small_element
			else:
				l -= 1
				small_element = small_element[:l]
		return -1


class Solution:

	def LCP(self, strs, n):
		min_str = min(strs, key=len)
		length = len(min_str)
		res = ''
		for i in range(length):
			prefix = strs[0]
			y = []
			t = 0
			for j in strs:
				y.append(j.startswith(prefix[:i + 1]))
			if all(y):
				res += prefix[i:i + 1]
		return res if res != '' else '-1'


class Solution:

	def LCP(self, strs, n):
		res = '-1'
		length = float('inf')
		arr = ''
		for i in range(len(strs)):
			if len(strs[i]) < length:
				length = len(strs[i])
				arr = strs[i]
		x = 0
		while x < length:
			for i in range(len(strs)):
				if strs[i][x] != arr[x]:
					return res
			x += 1
			res = arr[:x]
		return res