Strange LCS
Contest: Technocup 2022 - Elimination Round 2
Difficulty rating: 2600
Tags: bitmasks, dp, graphs, greedy, strings

You are given $$$n$$$ strings $$$s_1, s_2, \ldots, s_n$$$, each consisting of lowercase and uppercase English letters. In addition, it's guaranteed that each character occurs in each string at most twice. Find the longest common subsequence of these strings.

A string $$$t$$$ is a subsequence of a string $$$s$$$ if $$$t$$$ can be obtained from $$$s$$$ by deletion of several (possibly, zero or all) symbols.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10$$$) — the number of strings.

Each of the next $$$n$$$ lines contains the corresponding string $$$s_i$$$. Each $$$s_i$$$ is non-empty, consists only of uppercase and lowercase English letters, and no character appears more than twice in each string.

Output format:
For each test case print the answer in two lines:

In the first line print the length of the longest common subsequence.

In the second line print the longest common subsequence. If there are multiple such subsequences, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the longest common subsequence is "A". There are no common subsequences of length $$$2$$$.

In the second test case, sets of characters of strings don't intersect, so any non-empty string can't be a common subsequence.

Example input:
4
2
ABC
CBA
2
bacab
defed
3
abcde
aBcDe
ace
2
codeforces
technocup

Example output:
1
A
0

3
ace
3
coc

Editorial:
Let's define efinegraph with vertexes ($$$c$$$, $$$msk$$$), where $$$chr$$$ denoting some character, ans $$$mask$$$ is $$$n$$$-bit mask of occasions ($$$i$$$-th bit is set to $$$1$$$ if and only if we consider second occasion of $$$c$$$ in $$$i$$$-th string). Not all $$$mask$$$ are possible for some $$$c$$$ since there could be less than $$$2$$$ occasions. Note: vertex define choise of character and positions of this character in all strings.
Note, that graph has $$$\mathcal{O}(|\Sigma| \cdot 2^n)$$$ vertices.
Let's define strict comparison (<) of vertices:($$$chr1$$$, $$$msk1$$$) < ($$$char2$$$, $$$msk2$$$) if and only if positions chosen by first vertex are stricly lefter than ones chosen by second (for all strings). Let's define another comparison ($$$\leq$$$) the same way, but allow some position to be equal. Note: strict comparison is anti-reflexive, both comparison are transitive and this stands ($$$a$$$ $$$\leq$$$ $$$b$$$ < $$$c$$$ $$$\Rightarrow$$$ $$$a$$$ < $$$c$$$).
Graph contains directed edges from one vertex to another, if and only if first is smaller by defined comparison. Note: graph is acyclic, because of transitivity of pair comparison.
Note: that for every common subsequence there is unique corresponding path in defined graph and vice versa. So we need to find longest path in this graph. Vertex-length of path will be equal to the length of corresponding subsequence.
We want to calculate $$$dp$$$($$$c$$$, $$$msk$$$) – length of longest path starting from this vertex. This $$$dp$$$ is easy to calulate on DAG, but number of edges is too big. We want to remove some edges without changing values of $$$dp$$$. Note: if removal of edge doesn't change $$$dp$$$ of its starting point, when it doesn't change $$$dp$$$ at all.
Let's look at arbitrary vertex $$$(c, msk)$$$, that has at least one outgoing edge and some longest path starting from it (it has at least one edge): [$$$(c, msk) \rightarrow (c2, msk2) \rightarrow \ldots$$$]. Suppose there exists mask $$$MidMsk \neq msk2$$$, such that: (c, mask) < ($$$c2$$$, $$$MidMsk$$$) $$$\leq$$$ ($$$c2$$$, $$$msk2$$$). By the qualities of defined comparisons, we can change second vertex in longest path to ($$$c2$$$, $$$MidMsk$$$).
Now let's find mask for fixed $$$c2$$$ which correspond to choise of leftmost positions righter than positions chosen by ($$$c$$$, $$$msk$$$). It can be found in $$$\mathcal{O}(n)$$$ time. As we notices earlier, without loss of generality, longest path (with fixed $$$c2$$$) goes through this vertex , so we can harmlessly remove all edges going from current vertex to the vertices with character $$$c2$$$, but diffrent mask. This can be done for every character.
Now graph each vertex has $$$\mathcal{O}(|\Sigma|)$$$ outgoing edges, so $$$dp$$$ can be calculated fast enough. Subsequence itself can be easily found now.
Note: there is no need for graph in solution, it's just abstraction for better understanding.
Note: we don't have to calculate $$$dp$$$ for all vertices, we only need to find $$$dp(c, 0)$$$ for all $$$c$$$, it can be proven by applying same logic.
Overall complexity: $$$\mathcal{O}(n \cdot |\Sigma|^2 \cdot 2^n)$$$