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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.


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


Sample Output 1


Sample Input 2


Sample Output 2


Sample Input 3


Sample Output 3



There are no comments at the moment.