Another Contest 3 Problem 3 - Lexicographically Largest Common Subsequence

View as PDF

Submit solution


Points: 7
Time limit: 0.6s
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. If no nonempty 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.