Longest Common Subsequence for Multiple Strings

Given a list of strings, your task is to find the Longest Common Subsequence (LCS) among them. The LCS of a set of strings is defined as the longest sequence that can be obtained from every string by deleting some or no characters without changing the order of the remaining characters.

If more than one LCS exists with the same maximum length, you may output any of them. If there is no common subsequence among the strings, output an empty string.

Note: The answer must be computed using stdin for input and printed to stdout for output.

Mathematical formulation: Given strings \(S_1, S_2, \dots, S_n\), find a string \(L\) such that \(L\) is a subsequence of each \(S_i\) and \(|L|\) is maximized.

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 100\)) denoting the number of strings. The following \(n\) lines each contain a non-empty string composed of lowercase letters.

outputFormat

Output a single line containing the longest common subsequence among the given strings. If there is no common subsequence, output an empty string.

3
abcdefgh
aebdfh
abdfh

abdfh