Longest Common Subsequence Among Strings

You are given a set of strings and must compute the length of their longest common subsequence (LCS). The longest common subsequence is defined as the longest sequence that appears in the same relative order (not necessarily contiguous) in all the strings. For example, given strings abc, ac, and bca, the LCS is of length 1. Note that when only one string is provided, the LCS is the string itself, so its length is the length of that string.

In mathematical terms, if you have strings (S_1, S_2, \dots, S_n), you must find the largest integer (L) such that there exists a sequence (C = c_1, c_2, \dots, c_L) satisfying [ c_1, c_2, \dots, c_L \subseteq S_i \quad \text{for all } 1 \leq i \leq n, ] where the sequence (C) appears in each (S_i) in the same order. This problem is a classic in dynamic programming.

inputFormat

The first line of the input contains an integer (n), representing the number of strings. Each of the following (n) lines contains one non-empty string. Note that (n) can be 1, 2, or 3 for this problem.

outputFormat

Output a single integer, the length of the longest common subsequence among the given strings.## sample

3
abc
ac
bca

1