Let's start from some definitions.

Strings A and B are called anagrams if it's possible to rearrange the letters of string A using all the original letters exactly once and achieve string B; in other words A and B are permutations of each other. For example, remote and meteor are anagrams, race and race are anagrams as well, while seat and tease aren't anagrams as tease contains an extra 'e'.

String A is called a subsequence of string B if A can be obtained from B by removing some (possibly none) characters. For example, cat is a subsequence of scratch, rage is a subsequence of rage, and tame is not a subsequence of steam.

String A is lexicographically smaller than string B of the same length if at the first position where A and B differ A contains a letter which is earlier in the alphabet than the corresponding letter in B.

Recently, Ann received a set of strings consisting of small Latin letters a..z. 'What can I do with them?' -- she asked herself. 'What if I try to find the longest string which is a subsequence of every string from the set?'. Ann spent a lot of time trying to solve the problem... but all her attempts happened to be unsuccessful. She then decided to allow the sought string to be an anagram of some subsequence of every string from the set. This problem seemed to be easier to Ann, but she was too tired to solve it, so Ann asked for your help.

So your task is, given a set of strings, to find the longest non-empty string which satisfies Ann. Moreover, if there are many such strings, choose the lexicographically smallest one.

------ Input ------ 

The first line of the input file contains one integer N -- the number of strings in the set (1 ≤ N ≤ 100). Each of the next N lines contains a non-empty string consisting only of small Latin letters a..z representing a string from the set. None of the strings contain more than 100 letters.

------ Output ------ 

Output the longest non-empty string satisfying Ann. If there are several such strings, output the lexicographically smallest one. If there are no such strings, output 'no such string' (quotes for clarity).

----- Sample Input 1 ------ 
3
hope
elephant
path
----- Sample Output 1 ------ 
hp
----- explanation 1 ------ 
In the first test case the longest string appears to be two characters long. String 'hp' satisfies the requirements as it's an anagram of 'hp' which is a subsequence of 'hope' and an anagram of 'ph' which is a subsequence of both 'elephant' and 'path'. Note that string 'ph' also satisfies the requirements, but 'hp' is lexicographically smaller.

----- Sample Input 2 ------ 
2
wall
step
----- Sample Output 2 ------ 
no such string
----- explanation 2 ------ 
In this test case there is no such string.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures

Greedy algorithms


Solutions:
n = int(input())
s = input()
for i in range(n - 1):
	s1 = input()
	s2 = ''
	for j in s:
		if j in s2:
			continue
		c1 = s1.count(j)
		c2 = s.count(j)
		s2 += j * min(c1, c2)
	s = s2
if s == '':
	print('no such string')
else:
	print(''.join(sorted(s)))


l = []
for _ in range(int(input())):
	l.append(list(input()))
k = []
kk = []
for i in set(l[0]):
	tmp = []
	tmp2 = []
	for j in l:
		tmp.append(j.count(i))
	tmp2.append(i)
	k.append(min(tmp))
	kk.append(tmp2)
n = []
for i in range(len(k)):
	if k[i] != 0:
		n.append(kk[i][0] * k[i])
if len(n) != 0:
	n = sorted(n)
	print(''.join(n))
else:
	print('no such string')


a = None
for _ in range(int(input())):
	if a is None:
		a = input()
	else:
		b = input()
		temp = ''
		for i in set(a):
			temp += i * min(a.count(i), b.count(i))
		a = temp
if a == '':
	print('no such string')
else:
	print(''.join(sorted(a)))


n = int(input())
check = input()
for i in range(n - 1):
	checkin = input()
	empty = ''
	for j in check:
		if j in empty:
			continue
		checkcount = check.count(j)
		checkincount = checkin.count(j)
		empty += j * min(checkincount, checkcount)
	check = empty
if check:
	print(''.join(sorted(check)))
else:
	print('no such string')


n = int(input())
s = input()
for i in range(n - 1):
	x = input()
	t = ''
	for i in s:
		if i in t:
			continue
		y1 = s.count(i)
		y2 = x.count(i)
		t = t + i * min(y1, y2)
	s = t
if s == '':
	print('no such string')
else:
	print(''.join(sorted(s)))


from collections import Counter
arr = []
for i in range(int(input())):
	a = input()
	arr.append(a)
cn = Counter(arr[0])
for j in range(1, len(arr)):
	cn = Counter(arr[j]) & cn
if len(cn) == 0:
	print('no such string')
else:
	print(''.join(sorted(cn.elements())))


strings = []
for _ in range(int(input())):
	strings.append(input())
result = ''
if len(strings) == 0:
	print('no such string')
for letter in strings[0]:
	missing = 0
	for string in strings[1:]:
		if letter not in string:
			missing += 1
	if missing == 0:
		result += letter
		for i in range(1, len(strings)):
			strings[i] = strings[i].replace(letter, '', 1)
if len(result) == 0:
	print('no such string')
print(''.join(sorted(result)))


n = int(input())
s = input()
for _ in range(n - 1):
	x = input()
	t = ''
	for i in s:
		if i in t:
			continue
		y = s.count(i)
		l = x.count(i)
		t += i * min(y, l)
	s = t
if s == '':
	print('no such string')
else:
	print(''.join(sorted(s)))


from collections import defaultdict

def subanag(s):
	freq = [defaultdict(int) for _ in range(len(s))]
	for (i, j) in enumerate(s):
		for a in j:
			freq[i][a] += 1
	res = ''
	for a in sorted(freq[0].keys()):
		min_count = min((freq[i][a] for i in range(len(freq))))
		res += a * min_count
	return res if res else 'no such string'
n = int(input())
s = [input() for _ in range(n)]
print(subanag(s))


u = int(input())
strings = []
for x in range(u):
	strings.append(list(input()))

def answer(x):
	commonCharacters = set(x[0])
	for y in x[1:]:
		commonCharacters = set(y).intersection(commonCharacters)
		if len(commonCharacters) == 0:
			return 'no such string'
	string = ''
	for q in commonCharacters:
		freq = []
		for y in x:
			tmp = y.count(q)
			freq.append(tmp)
		string += q * min(freq)
	return ''.join(sorted(string))
print(answer(strings))


n = int(input())
res = [0 for i in range(26)]
for i in range(n):
	if i == 0:
		s = input()
		for char in s:
			res[ord(char) - 97] += 1
	else:
		curr = [0 for i in range(26)]
		s = input()
		for char in s:
			curr[ord(char) - 97] += 1
		for i in range(26):
			res[i] = min(res[i], curr[i])
ans = ''
for i in range(len(res)):
	if res[i] != 0:
		ans = ans + res[i] * chr(i + 97)
if len(ans) == 0:
	print('no such string')
else:
	print(ans)


n = int(input())
s = input()
for x in range(n - 1):
	a = input()
	d = ''
	for i in s:
		if i in d:
			continue
		d = d + i * min(s.count(i), a.count(i))
	s = d
if s == '':
	print('no such string')
else:
	print(''.join(sorted(s)))


count_list = []
for _ in range(int(input())):
	s = input()
	if count_list:
		for i in range(26):
			count_list[i] = min([count_list[i], s.count(chr(i + 97))])
	else:
		for i in range(26):
			count_list.append(s.count(chr(i + 97)))
ans = ''
for i in range(26):
	ans += chr(i + 97) * count_list[i]
print(ans if ans else 'no such string')


a = int(input())
s = input()
for i in range(a - 1):
	x = input()
	t = ''
	for i in s:
		if i in t:
			continue
		q1 = s.count(i)
		q2 = x.count(i)
		t += i * min(q1, q2)
	s = t
if s == '':
	print('no such string')
else:
	print(''.join(sorted(s)))


n = int(input())
x = []
for i in range(n):
	x.append(input())
y = ''
for i in list(map(chr, range(ord('a'), ord('z') + 1))):
	z = x[0].count(i)
	for word in x:
		if word.count(i) < z:
			z = word.count(i)
	y += i * z
print('no such string' if y == '' else y)


l = []
n = int(input())
for _ in range(n):
	l.append(input())
c = l[0]
for i in range(1, n):
	ans = ''
	for j in c:
		if j in ans:
			continue
		a = min(c.count(j), l[i].count(j))
		ans += j * a
	c = ans
print('no such string') if len(c) == 0 else print(''.join(sorted(c)))


value = []
for i in range(int(input())):
	value.append(input())
result = ''
for i in range(26):
	a = 1000
	letter = chr(i + 97)
	for j in value:
		if letter in j:
			a = min(a, j.count(letter))
		else:
			a = 0
			break
	result += letter * a
if result == '':
	print('no such string')
else:
	print(result)


t = int(input())
l = list()
for ni in range(t):
	l.append(input())
s = ''
for i in range(len(l[0])):
	a = l[0][i]
	c = 0
	for ni in range(1, t):
		if a in l[ni]:
			l[ni] = l[ni].replace(a, '', 1)
			c = c + 1
	if c == t - 1:
		s = s + a
s = list(s)
s.sort()
if len(s) == 0:
	print('no such string')
else:
	print(''.join(s))


from collections import Counter

def subanag(s):
	freq = Counter(s[0])
	for str in s:
		freq &= Counter(str)
	res = ''.join(sorted(list(freq.elements())))
	if res:
		return res
	else:
		return 'no such string'
n = int(input())
s = [input() for _ in range(n)]
print(subanag(s))


N = int(input())
Listy = []
for i in range(N):
	inp = input()
	Dict = {}
	for char in inp:
		if char in Dict:
			Dict[char] += 1
		else:
			Dict[char] = 1
	Listy.append(Dict)
Answer = []
for (key, value) in Listy[0].items():
	flag = True
	Vals = []
	Vals.append(value)
	for i in range(1, len(Listy)):
		if key in Listy[i]:
			flag = True
			Vals.append(Listy[i][key])
		else:
			flag = False
			Vals.clear()
			break
	if flag:
		Vals.sort()
		small = Vals[0]
		for j in range(0, small):
			Answer.append(key)
Answer.sort()
Return_Str = ''
for char in Answer:
	Return_Str += char
if len(Return_Str) != 0:
	print(Return_Str)
else:
	print('no such string')


n = int(input())
s = input()
for k in range(n - 1):
	p = input()
	d = ''
	for i in s:
		if i in d:
			continue
		k1 = s.count(i)
		k2 = p.count(i)
		d = d + i * min(k1, k2)
	s = d
if s == '':
	print('no such string')
else:
	print(''.join(sorted(s)))


n = int(input())
initial = input()
for i in range(n - 1):
	inp = input()
	intersect = ''
	for i in set(initial):
		if i in inp:
			intersect += i * min(initial.count(i), inp.count(i))
	initial = intersect
initial = sorted(initial)
if len(initial) == 0:
	print('no such string')
else:
	print(*initial, sep='')


n = int(input())
a = input()
for j in range(n - 1):
	b = input()
	d = ''
	for j in a:
		if j in d:
			continue
		x = a.count(j)
		y = b.count(j)
		d = d + j * min(x, y)
	a = d
if a == '':
	print('no such string')
else:
	print(''.join(sorted(a)))


from collections import Counter
numOfStr = int(input())
words = []
for i in range(numOfStr):
	words.append(input())
ans = Counter(words[0])
for i in range(1, numOfStr):
	ans = Counter(words[i]) & ans
if ans:
	ans = sorted(list(ans.elements()))
	print(*ans, sep='')
else:
	print('no such string')


from collections import Counter
t = int(input())
arr = []
for _ in range(t):
	s = input()
	arr.append(s)
counter = Counter(arr[0])
for i in range(1, len(arr)):
	counter = Counter(arr[i]) & counter
if len(counter) == 0:
	print('no such string')
else:
	print(''.join(sorted(counter.elements())))


N = int(input())
S = input()
for j in range(N - 1):
	S1 = input()
	P = ''
	for k in S:
		if k in P:
			continue
		k1 = S.count(k)
		k2 = S1.count(k)
		P = P + k * min(k1, k2)
	S = P
if S == '':
	print('no such string')
else:
	print(''.join(sorted(S)))


n = int(input())
st1 = input()
for i in range(n - 1):
	st2 = input()
	ans = ''
	for j in st1:
		if j in ans:
			continue
		a = st1.count(j)
		b = st2.count(j)
		ans += j * min(a, b)
	st1 = ans
if st1 == '':
	print('no such string')
else:
	print(''.join(sorted(st1)))


from collections import Counter
n = int(input())
l = []
for _ in range(n):
	l.append(input())
a = Counter(l[0])
for i in range(1, n):
	a = Counter(l[i]) & a
if a:
	a = sorted(list(a.elements()))
	print(*a, sep='')
else:
	print('no such string')


arr = [0] * 26
res_count = [100] * 26
ans = ''
t = int(input())
for _ in range(t):
	s = input().strip()
	d = {}
	for i in s:
		try:
			d[i] += 1
		except KeyError:
			d[i] = 1
	for i in d:
		if d[i] >= 1:
			arr[ord(i) - 97] += 1
			if d[i] < res_count[ord(i) - 97]:
				res_count[ord(i) - 97] = d[i]
for i in range(26):
	if arr[i] == t:
		ans += chr(i + 97) * res_count[i]
ans = sorted(ans)
if len(ans) > 0:
	p = ''
	for i in ans:
		p += i
	print(p)
else:
	print('no such string')


n = int(input())
s = input()
for i in range(n - 1):
	u = input()
	d = ''
	for i in s:
		if i in d:
			continue
		j1 = s.count(i)
		j2 = u.count(i)
		d = d + i * min(j1, j2)
	s = d
if s == '':
	print('no such string')
else:
	print(''.join(sorted(s)))


numberString = int(input())
string = input()
for _ in range(numberString - 1):
	OtherString = input()
	sample = ''
	for i in string:
		if i in sample:
			continue
		count1 = OtherString.count(i)
		count2 = string.count(i)
		sample += i * min(count1, count2)
	string = sample
if string == '':
	print('no such string')
else:
	print(''.join(sorted(string)))


n = int(input())
l = []
for i in range(n):
	s = input()
	set_s = set(s)
	l.append([set_s, s])
for j in range(n - 1):
	l[j + 1][0] = l[j + 1][0].intersection(l[j][0])
if len(l[-1][0]) == 0:
	print('no such string')
else:
	(l_count, s_final) = ([], '')
	for elem in l[-1][0]:
		l1 = []
		for x in range(n):
			l1.append(l[x][1].count(elem))
		l1.sort()
		l_count.append(elem * l1[0])
	l_count.sort()
	for y in range(len(l_count)):
		s_final = s_final + l_count[y]
	print(s_final)


N = int(input())
listOfWords = []
for _ in range(N):
	listOfWords.append(input())
commonWord = ''
for letter in list(map(chr, range(ord('a'), ord('z') + 1))):
	minNumLetter = listOfWords[0].count(letter)
	for word in listOfWords:
		if word.count(letter) < minNumLetter:
			minNumLetter = word.count(letter)
	commonWord += letter * minNumLetter
if commonWord == '':
	print('no such string')
else:
	print(commonWord)