Strange LCS (Codeforces 1584F)
Tags: 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: 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: 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.

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.

Sample Inputs:
4
2
ABC
CBA
2
bacab
defed
3
abcde
aBcDe
ace
2
codeforces
technocup

Sample Outputs:
1
A
0

3
ace
3
coc

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input().rstrip())
letters = [chr(ch) for ch in range(ord('a'), ord('z') + 1)] + [chr(ch) for ch in range(ord('A'), ord('Z') + 1)]
nlet = len(letters)
ch2ind = {ch: i for (i, ch) in enumerate(letters)}

def nbs(c, msk):
    positions = [c2positions[c][i][1 if msk & 1 << i else 0] for i in range(n)]
    nbs = []
    for c2 in range(nlet):
        msk2 = 0
        for i in range(n):
            lc2 = len(c2positions[c2][i])
            if lc2 > 0 and positions[i] < c2positions[c2][i][0]:
                msk2 |= 0
            elif lc2 > 1 and positions[i] < c2positions[c2][i][1]:
                msk2 |= 1 << i
            else:
                msk2 = -1
                break
        if msk2 != -1:
            nbs.append((c2, msk2))
    return nbs

def rec(c, msk):
    if (c, msk) not in dp:
        mx = 1
        next_ch = (-1, -1)
        for (c2, msk2) in nbs(c, msk):
            val = rec(c2, msk2)[0] + 1
            if mx < val:
                mx = val
                next_ch = (c2, msk2)
        dp[c, msk] = (mx, next_ch)
    return dp[c, msk]
for _ in range(t):
    n = int(input().rstrip())
    s = []
    for __ in range(n):
        s.append(input().rstrip())
    c2positions = [[[] for i in range(n)] for l in range(nlet)]
    for i in range(n):
        for (j, ch) in enumerate(s[i]):
            c2positions[ch2ind[ch]][i].append(j)
    available_letters = set.intersection(*[set(ss) for ss in s])
    if len(available_letters) == 0:
        print(0)
        print()
        continue
    dp = {}
    (mx, c) = max(((rec(ch2ind[c], 0)[0], ch2ind[c]) for c in available_letters))
    msk = 0
    ans = ''
    while c != -1:
        ans += letters[c]
        (c, msk) = dp[c, msk][1]
    print(mx)
    print(ans)

Solution (Python):
from string import ascii_lowercase, ascii_uppercase

def memoization(idxs, c, mask, dp):
    if dp[c][mask][0] == -1:
        dp[c][mask] = (0, c, mask)
        for nc in range(len(ALPHA_TO_INT)):
            (ok, new_mask) = (True, 0)
            for (i, idx) in enumerate(idxs):
                j = idx[c][(mask >> i) % 2]
                if idx[nc][0] > j:
                    new_mask |= 0 << i
                    continue
                if idx[nc][1] > j:
                    new_mask |= 1 << i
                    continue
                ok = False
                break
            if not ok:
                continue
            l = memoization(idxs, nc, new_mask, dp)[0] + 1
            if l > dp[c][mask][0]:
                dp[c][mask] = (l, nc, new_mask)
    return dp[c][mask]

def solution():
    n = int(input())
    idxs = [[[-1] * 2 for _ in range(len(ALPHA_TO_INT))] for _ in range(n)]
    for idx in idxs:
        s = input().strip()
        for (i, c) in enumerate(s):
            c = ALPHA_TO_INT[c]
            if idx[c][0] == -1:
                idx[c][0] = i
            else:
                idx[c][1] = i
    dp = [[(-1,) * 3 for _ in range(2 ** n)] for _ in range(len(ALPHA_TO_INT))]
    (max_l, max_c) = (0, -1)
    for c in range(len(ALPHA_TO_INT)):
        if any((idx[c][0] == -1 for idx in idxs)):
            continue
        l = memoization(idxs, c, 0, dp)[0] + 1
        if l > max_l:
            (max_l, max_c) = (l, c)
    result = []
    (c, mask) = (max_c, 0)
    for _ in range(max_l):
        result.append(INT_TO_ALPHA[c])
        (c, mask) = dp[c][mask][1:]
    return '%s\n%s' % (len(result), ''.join(result))
(ALPHA_TO_INT, INT_TO_ALPHA) = ({}, {})
for (i, c) in enumerate(ascii_lowercase):
    (ALPHA_TO_INT[c], INT_TO_ALPHA[i]) = (i, c)
for (i, c) in enumerate(ascii_uppercase, len(ascii_lowercase)):
    (ALPHA_TO_INT[c], INT_TO_ALPHA[i]) = (i, c)
for case in range(int(input())):
    print('%s' % solution())

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input().rstrip())
letters = [chr(ch) for ch in range(ord('a'), ord('z') + 1)] + [chr(ch) for ch in range(ord('A'), ord('Z') + 1)]
nlet = len(letters)
ch2ind = {ch: i for (i, ch) in enumerate(letters)}

def nbs(c, msk):
    positions = [c2positions[c][i][1 if msk & 1 << i else 0] for i in range(n)]
    nbs = []
    for c2 in range(nlet):
        msk2 = 0
        for i in range(n):
            lc2 = len(c2positions[c2][i])
            if lc2 > 0 and positions[i] < c2positions[c2][i][0]:
                msk2 |= 0
            elif lc2 > 1 and positions[i] < c2positions[c2][i][1]:
                msk2 |= 1 << i
            else:
                msk2 = -1
                break
        if msk2 != -1:
            nbs.append((c2, msk2))
    return nbs

def rec(c, msk):
    if (c, msk) not in dp:
        mx = 1
        next_ch = (-1, -1)
        for (c2, msk2) in nbs(c, msk):
            val = rec(c2, msk2)[0] + 1
            if mx < val:
                mx = val
                next_ch = (c2, msk2)
        dp[c, msk] = (mx, next_ch)
    return dp[c, msk]
for _ in range(t):
    n = int(input().rstrip())
    s = []
    for __ in range(n):
        s.append(input().rstrip())
    c2positions = [[[] for i in range(n)] for l in range(nlet)]
    for i in range(n):
        for (j, ch) in enumerate(s[i]):
            c2positions[ch2ind[ch]][i].append(j)
    available_letters = set.intersection(*[set(ss) for ss in s])
    if len(available_letters) == 0:
        print(0)
        print()
        continue
    dp = {}
    (mx, c) = max(((rec(ch2ind[c], 0)[0], ch2ind[c]) for c in available_letters))
    msk = 0
    ans = ''
    while c != -1:
        ans += letters[c]
        (c, msk) = dp[c, msk][1]
    print(mx)
    print(ans)