Another Contest 3 Problem 3 - Lexicographically Largest Common Subsequence

View as PDF

Submit solution


Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem types

Given N strings of lowercase letters, compute the lexicographically largest string that is a subsequence of all N strings.

String s is a subsequence of string t if s can be obtained by deleting some of the letters in t. It is not required to delete any letters.

String s is lexicographically larger than t if t is a prefix of s or, given that index i is the first mismatch in strings s and t, the ith character of s is larger than the ith character of t.

Constraints

1 \le N \le 10^5

The sum of the lengths of all strings will be at most 10^6.

All strings will only contain lowercase letters.

Input Specification

The first line contains a single positive integer, N.

The next N lines each contain a string of lowercase letters. The string is guaranteed to contain at least one letter.

Output Specification

Output the lexicographically largest common subsequence. In the event no nonempty such subsequence exists, output -1.

Sample Input 1

2
quantum
xyene

Sample Output 1

n

Sample Input 2

1
cba

Sample Output 2

cba

Sample Input 3

3
a
ab
c

Sample Output 3

-1

Comments

There are no comments at the moment.