Subanagrams

Problem code: SUBANAGR

All submissions for this problem are available.

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).

Example

Input:
3
hope
elephant
path

Output:
hp

Input:
2
wall
step

Output:
no such string

Explanation:
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.

In the second test case there is no such string.

Author: gennady.korotkevich
Date Added: 4-11-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

can substring have same

biraj_patel @ 20 Nov 2011 09:40 PM
can substring have same characters repeated as in can substring be "hpp" ?

@biraj_patel Yes it can.

anton_adm @ 20 Nov 2011 09:43 PM
@biraj_patel Yes it can.

thks

biraj_patel @ 20 Nov 2011 09:48 PM
thks

why tame is not a subsequence

avinash1 @ 20 Nov 2011 10:40 PM
why tame is not a subsequence of steam?

@avinash1. Because we can not

anton_adm @ 20 Nov 2011 10:43 PM
@avinash1. Because we can not change order of letters when form a subsequence. We can erase 's' in order to obtain 'team' but then we can't rearrange letters to obtain 'tame'. It is forbidden by definition. However 'tame' is a subanagram of 'steam'.

is the answer a

shishirgarg @ 20 Nov 2011 10:44 PM
is the answer a subsequence(not anagram of subsequence) of at least one input strings or is that not necessary?

@shishirgarg. It is not

anton_adm @ 20 Nov 2011 10:46 PM
@shishirgarg. It is not necessary. See explanation of first example.

@shishirgarg. Sorry I didn't

anton_adm @ 20 Nov 2011 10:47 PM
@shishirgarg. Sorry I didn't get your question completely. First example is a bad reference. But the answer is the same: it is not necessary.

So if I understood the

randomusername @ 20 Nov 2011 10:52 PM
So if I understood the problem well.... all the chars from answer_string must be in every input_string, order doesn't matter, right?

@randomusername. Yes, you are

anton_adm @ 20 Nov 2011 10:58 PM
@randomusername. Yes, you are right. But this is a big hint. So I will post your comment only after the contest.

I was trying to solve this

shishirgarg @ 23 Nov 2011 02:22 PM
I was trying to solve this during the contest but only managed to finish now. can't we submit our solutions now for practice?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions