Given an array of N strings, find the longest common prefix among all strings present in the array.
Example 1:
Input:
N = 4
arr[] = {geeksforgeeks, geeks, geek,
         geezer}
Output: gee
Explanation: "gee" is the longest common
prefix in all the given strings.
Example 2:
Input: 
N = 2
arr[] = {hello, world}
Output: -1
Explanation: There's no common prefix
in the given strings.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestCommonPrefix() which takes the string array arr[] and its size N as inputs and returns the longest common prefix common in all the strings in the array. If there's no prefix common in all the strings, return "-1".
Expected Time Complexity: O(N*min(|arr_{i}|)).
Expected Auxiliary Space: O(min(|arr_{i}|)) for result.
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ |arr_{i}| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def longestCommonPrefix(self, arr, n):

        # code here

Solutions:
class Solution:

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


class Solution:

	def longestCommonPrefix(self, arr, n):
		smallest = arr[0]
		for i in range(1, n):
			if len(arr[i]) < len(smallest):
				smallest = arr[i]
		while True:
			flag = 0
			for ele in arr:
				if smallest not in ele[0:len(smallest)]:
					smallest = smallest[:len(smallest) - 1]
					flag = 1
					break
			if len(smallest) == 0:
				return '-1'
			elif flag == 0:
				return smallest


class Solution:

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


class Solution:

	def longestCommonPrefix(self, arr, n):
		pre = ''
		k = 0
		while True:
			s = arr[0][k]
			flag = False
			for i in arr:
				if i[k] == s:
					continue
				else:
					flag = True
					break
			if flag == False:
				pre += s
				if k < len(min(arr)) - 1:
					k += 1
				else:
					break
			else:
				break
		if pre == '':
			return -1
		return pre


class Solution:

	def longestCommonPrefix(self, arr, n):
		a = min(arr)
		b = ''
		for i in range(len(a)):
			for j in range(1, n):
				if a[i] != arr[j][i]:
					if b == '':
						return -1
					else:
						return b
			b += a[i]
		return b


class Solution:

	def longestCommonPrefix(self, arr, n):
		if not arr:
			return -1
		idx = 0
		mini = float('inf')
		w = ''
		for word in arr:
			if len(word) < mini:
				mini = len(word)
				w = word
		comp = mini
		res = ''
		while idx < mini:
			ele = w[idx]
			for word in arr:
				if ele != word[idx]:
					return res if res else -1
			res += ele
			idx += 1
		return res if res else -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		if not arr:
			return ''
		arr.sort()
		last = arr[len(arr) - 1]
		first = arr[0]
		common = ''
		for i in range(len(first)):
			if first[i] != last[i]:
				break
			common += first[i]
		if common == '':
			return -1
		return common


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr.sort()
		s = arr[0]
		sum = ''
		for i in range(len(s)):
			if s[i] == arr[n - 1][i]:
				sum += s[i]
			else:
				break
		return sum if len(sum) > 0 else -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		a = min(arr)
		c = ''
		d = []
		arr.remove(a)
		if n == 1:
			return a
		else:
			for i in arr:
				for j in range(len(a)):
					if a[j] == i[j]:
						c += a[j]
					else:
						break
				d.append(c)
				c = list(c)
				c.clear()
				c = str(c)
			q = min(d)
			if n > 2:
				g = q[2:]
			else:
				g = q[:]
		if len(g) == 0:
			return -1
		else:
			return g


class Solution:

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


class Solution:

	def longestCommonPrefix(self, arr, n):
		size = len(arr)
		if size == 0:
			return ''
		if size == 1:
			return arr[0]
		arr.sort()
		end = min(len(arr[0]), len(arr[size - 1]))
		s = ''
		if arr[0][0] != arr[size - 1][0]:
			return -1
		for i in range(end):
			j = 0
			if arr[j][i] == arr[n - 1][i]:
				s = s + str(arr[j][i])
				j = j + 1
		return s


class Solution:

	def longestCommonPrefix(self, arr, n):
		ans = ''
		for chars in zip(*arr):
			c = chars[0]
			for char in chars[1:]:
				if char != c:
					if len(ans) == 0:
						return -1
					else:
						return ans
			ans = ans + c
		return ans


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr = sorted(arr, key=len)
		s1 = arr[0]
		s = ''
		dic = {}
		arr = arr[1:]
		for i in s1:
			s += i
			dic[s] = 1
		dic = sorted(dic.items())
		ans = ''
		for i in dic:
			flag = True
			a = len(i[0])
			for j in arr:
				if j[:a] == i[0]:
					pass
				else:
					flag = False
					break
			if flag == True:
				ans = i[0]
		if ans:
			return ans
		return -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		lm = -1
		for i in range(len(arr[0])):
			for j in range(len(arr)):
				if i >= len(arr[j]) or arr[0][i] != arr[j][i]:
					if lm != -1:
						return arr[0][0:lm + 1]
					else:
						return -1
			lm = i
		return arr[0][0:lm + 1]


class Solution:

	def longestCommonPrefix(self, arr, n):
		a = min(arr, key=len)
		x = len(a)
		arr1 = [word[0:x] for word in arr]
		for i in range(3, 0, -1):
			if len(set(arr1)) == 1:
				return arr1[0]
				break
			arr1 = [word[0:i] for word in arr1]
		return '-1'


class Solution:

	def longestCommonPrefix(self, strs, n):
		arr.sort()
		less = arr[0]
		output = ''
		for i in range(len(less)):
			if arr[0][i] == arr[n - 1][i]:
				output += arr[0][i]
			else:
				break
		return output if output else -1


class Solution:

	def longestCommonPrefix(self, strs, n):
		s = ''
		for i in range(len(strs[0])):
			less = strs[0][i]
			for word in strs:
				if i == len(word) or word[i] != less:
					if len(s) == 0:
						return -1
					return s
			s = s + less
		return s


class Solution:

	def longestCommonPrefix(self, strs, n):
		s = ''
		for i in range(len(strs[0])):
			c = strs[0][i]
			for j in strs:
				if i == len(j) or j[i] != c:
					if len(s) == 0:
						return -1
					return s
			s = s + c
		return s


class Solution:

	def longestCommonPrefix(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort(key=len)
		a = arr[0]
		k = len(a)
		t = 0
		for i in range(1, n):
			c = 0
			r = i
			p = arr[i]
			for j in range(k):
				if a[j] == p[j]:
					c += 1
				else:
					break
			if r == 1:
				t = c
			if t > c:
				t = c
		if t == 0:
			return -1
		else:
			return a[:t]


class Solution:

	def longestCommonPrefix(self, arr, n):
		min_len = 0
		for i in arr:
			if min_len == 0 or len(i) < min_len:
				min_len = len(i)
				min_word = i
		common = ''
		for i in range(min_len):
			c = 0
			for j in arr:
				if j[:i + 1] == min_word[:i + 1]:
					c += 1
			if c != n:
				break
			common += min_word[i]
		return -1 if common == '' else common


class Solution:

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


class Solution:

	def longestCommonPrefix(self, string_list, n):
		min_str_len = len(string_list[0])
		for tmp_string in string_list:
			if len(tmp_string) <= min_str_len:
				min_str_len = len(tmp_string)
				short_string = tmp_string
		for tmp_min_str_len in reversed(range(1, min_str_len + 1)):
			matching_str_count = 0
			for tmp_string in string_list:
				tmp_string_crop = tmp_string[:tmp_min_str_len]
				short_string_crop = short_string[:tmp_min_str_len]
				if tmp_string_crop == short_string_crop:
					matching_str_count += 1
					if matching_str_count == n:
						return short_string_crop
				else:
					break
		return -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr = sorted(arr)
		s = arr[0]
		c = 0
		if len(s) == 1:
			for i in arr:
				if s in i:
					c = c + 1
			if c == len(arr):
				return s
			else:
				return -1
		else:
			l = []
			for i in range(len(s)):
				if i <= 0:
					for j in range(i + 2, len(s) + 1):
						s1 = s[i:j]
						d = 0
						for k in arr:
							if s1 in k:
								d = d + 1
						if d == len(arr):
							l.append(s1)
			if len(l) == 0:
				return -1
			else:
				f = l[::-1]
				return f[0]


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr = sorted(arr)
		temp = arr[0]
		item = arr[n - 1]
		s = ''
		for (cr, cr1) in zip(item, temp):
			if cr == cr1:
				s += cr
			else:
				break
		if not s:
			return -1
		else:
			return s


class Solution:

	def longestCommonPrefix(self, arr, n):
		temp = arr[0]
		s = ''
		flag = 0
		sos = True
		for item in arr[1:]:
			for (cr, cr1) in zip(item, temp):
				if cr == cr1:
					s += cr
					temp = s
					flag = 1
				else:
					break
			if flag == 0:
				sos = False
			s = ''
			flag = 0
		if not sos:
			return -1
		else:
			return temp


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr.sort()
		res = ''
		i = 0
		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 = i + 1
		return res


class Solution:

	def longestCommonPrefix(self, arr, n):
		mini = min(arr, key=len)
		stri = []
		for k in range(len(mini)):
			match = True
			for i in arr:
				if list(i)[k] != list(mini)[k]:
					match = False
					break
			if match == False:
				break
			else:
				stri.append(list(i)[k])
		if stri:
			return ''.join(stri)
		else:
			return -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		min_length = len(arr[0])
		string = ''
		for i in range(1, n):
			min_length = min(len(arr[i]), min_length)
		for i in range(min_length):
			for j in range(1, n):
				if arr[j - 1][i] != arr[j][i]:
					return string if string else -1
			string += arr[0][i]
		return string if string else -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		prefix = arr[0]
		for i in range(1, len(arr)):
			j = 0
			while j < len(prefix) and j < len(arr[i]) and (prefix[j] == arr[i][j]):
				j += 1
			prefix = prefix[:j]
			if not prefix:
				return -1
		return prefix


class Solution:

	def longestCommonPrefix(self, arr, n):
		c = 0
		s = ''
		for i in range(len(arr[0])):
			g = arr[0][i]
			f = -1
			for j in range(n):
				if i < len(arr[j]):
					if arr[j][i] == g:
						f = 1
					elif i == 0:
						return -1
					else:
						return s
				else:
					return s
			if f == 1:
				s += g
				c += 1
		if c > 0:
			return s
		else:
			return -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		ans = ''
		for i in range(n):
			if i == 0:
				ans = arr[i]
			else:
				cur_pos = 0
				new_ans = ''
				while cur_pos < len(arr[i]) and cur_pos < len(ans) and (arr[i][cur_pos] == ans[cur_pos]):
					new_ans += arr[i][cur_pos]
					cur_pos += 1
				ans = new_ans
		return ans if ans != '' else '-1'


class Solution:

	def longestCommonPrefix(self, arr, n):
		min_word = arr[0]
		min_length = len(arr[0])
		for word in arr:
			word_length = len(word)
			if word_length < min_length:
				min_word = word
				min_length = word_length
		for i in range(min_length, 0, -1):
			prefix = min_word[:i]
			startswith_prefix_predicate = lambda x: x.startswith(prefix)
			filtered_list = list(filter(startswith_prefix_predicate, arr))
			if len(filtered_list) == len(arr):
				return prefix
		return -1


class Solution:

	def leastlen(self, arr, n):
		min1 = len(arr[0])
		for i in range(1, n):
			if len(arr[i]) < min1:
				min1 = len(arr[i])
		return min1

	def longestCommonPrefix(self, arr, n):
		mini = self.leastlen(arr, n)
		s = ''
		for i in range(mini):
			ans = arr[0][i]
			for j in range(1, n):
				if ans != arr[j][i]:
					if s != '':
						return s
					else:
						return -1
			s += ans
		return s


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr.sort(key=lambda x: len(x))
		prefix = arr[0]
		i = 1
		while i < n:
			j = 0
			m = len(prefix)
			while j < m and prefix[j] == arr[i][j]:
				j += 1
			i += 1
			if j == 0:
				return -1
			prefix = prefix[:j]
		return prefix


class Solution:

	def longestCommonPrefix(self, arr, n):
		i = 0
		l = min([len(x) for x in arr])
		valid = True
		first = arr[0]
		while i < l and valid:
			curr = first[i]
			for word in arr[1:]:
				if word[i] != curr:
					if i == 0:
						return -1
					valid = False
			if valid:
				i += 1
		return first[:i]


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr = sorted(arr)
		e = ''
		l = arr[0]
		s = arr[-1]
		for j in range(len(l)):
			if l[j] != s[j]:
				break
			else:
				e += l[j]
		if len(e) == 0:
			return -1
		else:
			return e


class Solution:

	def longestCommonPrefix(self, arr, n):
		if n == 1:
			return arr[0]
		else:
			mi = min([len(s) for s in arr])
			ans = 0
			cnt = 0
			for j in range(mi):
				if arr[1][j] != arr[0][j]:
					break
				cnt += 1
			ans = cnt
			for i in range(1, n):
				cnt = 0
				for j in range(mi):
					if j == 0 and arr[i][j] != arr[0][j]:
						return -1
					elif arr[i][j] != arr[0][j]:
						if cnt < ans:
							ans = cnt
						break
					cnt += 1
			return arr[0][:ans]


class Solution:

	def longestCommonPrefix(self, arr, n):
		s = ''
		for j in range(1000):
			d = {}
			for i in range(n):
				if j < len(arr[i]):
					d[arr[i][j]] = 0
				else:
					return s if s != '' else -1
			if len(d) == 1:
				s += list(d.keys())[0]
			else:
				return s if s != '' else -1
		return s if s != '' else -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		m = float('inf')
		for i in range(n):
			m = min(m, len(arr[i]))
		flg = 0
		l = 0
		for i in range(m):
			for j in range(n - 1):
				if arr[j][i] != arr[j + 1][i]:
					flg = 1
					break
			if flg == 1:
				break
			l += 1
		return -1 if l == 0 else arr[0][:l]


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr.sort(key=lambda x: len(x))
		ans = arr[0]
		l = 0
		for i in arr:
			c = 0
			m = 0
			while c < len(ans) and ans[c] == i[c]:
				c += 1
			ans = ans[:c]
		if len(ans) > 0:
			return ans
		return -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		ans = ''
		l = 0
		false = False
		while l < len(arr[0]):
			for i in range(1, n):
				if l > len(arr[i]) - 1 or arr[0][:l + 1] != arr[i][:l + 1]:
					false = True
					break
			if false:
				break
			else:
				ans += arr[0][l]
			l += 1
		if ans == '':
			return -1
		else:
			return ans


class Solution:

	def longestCommonPrefix(self, arr, n):
		min_ar = len(arr[0])
		min_word = arr[0]
		for i in range(n):
			if len(arr[i]) < min_ar:
				min_ar = len(arr[i])
				min_word = arr[i]
		for i in range(min_ar):
			m = min_word[i]
			for j in range(n):
				if m != arr[j][i]:
					if len(min_word[:i]) > 1:
						return min_word[:i]
					else:
						return -1
		return min_word


class Solution:

	def longestCommonPrefix(self, arr, n):
		res = ''
		first = arr[0]
		for c in range(len(first)):
			for s in arr:
				if c >= len(s) or not s[c] == first[c]:
					return res or '-1'
			res += first[c]
		return res or '-1'


class Solution:

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


class Solution:

	def longestCommonPrefix(self, arr, n):
		arr.sort(key=len)
		mm = arr[0]
		m = len(mm)
		for i in range(m, 0, -1):
			mn = mm[:i]
			for j in arr:
				if j[:i] != mn:
					break
			else:
				return mn
		return '-1'


class Solution:

	def longestCommonPrefix(self, arr, n):
		res = ''
		k = min(arr, key=len)
		for i in range(len(k)):
			temp = arr[0][i]
			for word in arr:
				if word[i] != temp:
					if not res:
						return -1
					else:
						return res
			res += temp
		return res


class Solution:

	def longestCommonPrefix(self, arr, n):
		res = arr[0]
		for i in range(1, n):
			curr = arr[i]
			(j, k) = (0, 0)
			while j < len(res) and k < len(curr):
				if res[j] != curr[k]:
					break
				j += 1
				k += 1
			res = res[:j]
			if not res:
				return '-1'
		return res


class Solution:

	def longestCommonPrefix(self, arr, n):
		s1 = '-1'
		m = 1000
		for i in range(n):
			l = len(arr[i])
			if l < m:
				s1 = arr[i]
				m = l
			else:
				m = m
		for i in range(m - 1, -1, -1):
			c = 0
			for j in range(n):
				if s1 not in arr[j]:
					s1 = s1[0:i:1]
					break
				elif arr[j][0] == s1[0]:
					c += 1
			if c == n:
				return s1
		return '-1'


class Solution:

	def longestCommonPrefix(self, arr, n):
		s = ''
		k = 0
		lst = [len(i) for i in arr]
		mini = min(lst)
		while k < mini:
			f = arr[0][k]
			for i in arr:
				if i[k] != f:
					return s if len(s) != 0 else -1
			s += f
			k += 1
		return s


class Solution:

	def longestCommonPrefix(self, arr, n):
		max_value = 0
		comm_prefix = ''
		long_word_index = -1
		if n == 1:
			return arr[0]
		for (index, word) in enumerate(arr):
			if len(word) > max_value:
				max_value = len(word)
				longest_word = word
				long_word_index = index
		for i in range(max_value):
			prefix = ''
			for (index, word) in enumerate(arr):
				if long_word_index == index:
					continue
				if i < len(word) and longest_word[i] == word[i]:
					prefix = longest_word[i]
				else:
					prefix = ''
					break
			if prefix != '' and len(prefix) <= len(longest_word):
				comm_prefix += prefix
			elif prefix == '':
				break
		if comm_prefix == '':
			return -1
		else:
			return comm_prefix


class Solution:

	def longestCommonPrefix(self, arr, n):
		s1 = ''
		lst = []
		if len(arr) == 1:
			return arr[0]
		if len(arr) == 0:
			return -1
		for i in range(n - 1):
			if i == 0:
				l = min(len(arr[i]), len(arr[i + 1]))
			else:
				l = min(len(s1), len(arr[i + 1]))
			s2 = ''
			for j in range(l):
				if i == 0:
					if arr[i][j] == arr[i + 1][j]:
						s1 = s1 + arr[i][j]
				elif i >= 1 and s1[0] == arr[0][0]:
					if s1[j] == arr[i + 1][j]:
						s2 = s2 + s1[j]
				else:
					return -1
			if s1 == '':
				return '-1'
			if i != 0:
				s1 = s2
			lst.append(s1)
		return s1


class Solution:

	def longestCommonPrefix(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		a = ''
		leng = len(arr[0])
		for i in range(len(arr)):
			leng = min(leng, len(arr[i]))
		for i in range(leng):
			an = arr[0][i]
			for j in range(len(arr)):
				if an == arr[j][i]:
					continue
				elif a == '':
					return -1
				else:
					return a
			a = a + an
		return a


class Solution:

	def longestCommonPrefix(self, arr, n):
		smallset = arr[0]
		for word in arr:
			if len(word) < len(smallset):
				smallset = word
		prefix = ''
		i = 0
		for char in smallset:
			check = 1
			for word in arr[:]:
				if len(word) > i:
					if word[i] != char:
						check = 0
						break
			i += 1
			if check:
				prefix += char
			else:
				break
		if prefix == '':
			return -1
		return prefix


class Solution:

	def longestCommonPrefix(self, arr, n):
		prefix = ''
		i = 0
		if len(arr) <= 1:
			return arr[0]
		char_to_be_compared = arr[0][0]
		while True:
			for j in range(1, len(arr)):
				if i < len(arr[j]) and arr[j][i] is not char_to_be_compared:
					if len(prefix) == 0:
						return '-1'
					else:
						return prefix
				elif i >= len(arr[j]):
					if len(prefix) == 0:
						return '-1'
					else:
						return prefix
			prefix += arr[j][i]
			i += 1
			if i < len(arr[0]):
				char_to_be_compared = arr[0][i]
			elif len(prefix) == 0:
				return '-1'
			else:
				return prefix


class Solution:

	def longestCommonPrefix(self, arr, n):
		res = arr[0]
		for _str in arr:
			if res == '':
				break
			tmp_res = res
			res = ''
			for i in range(min(len(_str), len(tmp_res))):
				if tmp_res[i] == _str[i]:
					res += _str[i]
				else:
					break
		if res == '':
			return -1
		return res


class Solution:

	def longestCommonPrefix(self, arr, n):
		mi = len(arr[0])
		for i in range(n):
			if mi > len(arr[i]):
				mi = len(arr[i])
		res = ''
		for i in range(mi):
			ele = arr[0][i]
			j = 0
			mi = 0
			count = 0
			while j != n:
				if ele == arr[j][i]:
					count += 1
				j += 1
			if count == n:
				res += arr[0][i]
			else:
				break
		if res == '':
			return -1
		return res


class Solution:

	def longestCommonPrefix(self, arr, n):
		maximum_length_prefix = len(arr[0])
		prefix = ''
		for ele in arr:
			if maximum_length_prefix >= len(ele):
				maximum_length_prefix = len(ele)
				prefix = ele
		for ele in arr:
			change_prefix_length = 0
			prefix_ = ''
			for i in range(maximum_length_prefix):
				if ele[i] == prefix[i]:
					change_prefix_length += 1
					prefix_ += ele[i]
				else:
					break
			maximum_length_prefix = change_prefix_length
			prefix = prefix_
		return prefix if prefix else -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		out = arr[0]
		for i in arr:
			while out != '':
				if out not in i[:len(out)]:
					out = out[:-1]
				else:
					break
		if out == '':
			return -1
		return out


class Solution:

	def longestCommonPrefix(self, arr, n):
		ans = ''
		for i in range(len(arr[0])):
			for j in arr:
				if i >= len(j):
					if len(ans) == 0:
						return -1
					return ans
				if j[i] != arr[0][i]:
					if len(ans) == 0:
						return -1
					return ans
			ans += arr[0][i]
		return ans


class Solution:

	def longestCommonPrefix(self, arr, n):
		m = len(arr[0])
		j = 0
		for i in range(1, n):
			if len(arr[i]) < m:
				j = i
				m = len(arr[j])
		for i in range(m, 0, -1):
			f = 1
			for k in range(n):
				if arr[k][:i] != arr[j][:i]:
					f = 0
					break
			if f == 1:
				return arr[j][:i]
		return -1


class Solution:

	def longestCommonPrefix(self, arr, n):
		(temp, answer) = ('', '')
		if n == 1:
			return arr[0]
		for i in range(min(len(arr[0]), len(arr[1]))):
			if arr[0][i] == arr[1][i]:
				temp += arr[0][i]
			else:
				break
		if n == 2:
			return temp
		for i in range(2, n):
			for j in range(min(len(temp), len(arr[i]))):
				if temp[j] == arr[i][j]:
					answer += temp[j]
				else:
					temp = answer
					break
			temp = answer
			answer = ''
		if temp == '':
			return -1
		else:
			return temp