MINLCS - Editorial

Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh

TBD

None

PROBLEM:

Given two strings A and B, rearrange them so that the length of their longest common subsequence is minimized.

EXPLANATION:

Consider some character \alpha. Let it occur f_A(\alpha) times in A and f_B(\alpha) times in B. Then, the length of LCS(A, B) is at least \min(f_A(\alpha), f_B(\alpha)), no matter how they are rearranged.

Proof

This should be obvious: simply consider the subsequence consisting only of this character. It has length \min(f_A(\alpha), f_B(\alpha)), and is present no matter what the rearrangement is.

This means the answer is, at the very least, the maximum value of \min(f_A(\alpha), f_B(\alpha)) across all characters \alpha from a to z.

It turns out that this is exactly the answer: if you sort A in ascending order and B in descending order, then there are no common subsequences with more than one distinct letter, so the answer is simply the longest common subsequence consisting of a single letter.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python)
import collections
for _ in range(int(input())):
n = int(input())
a = input()
b = input()
d1, d2 = collections.Counter(a), collections.Counter(b)
ans = 0
for c in 'qwertyuiopasdfghjklzxcvbnm':
if c not in d1 or c not in d2: continue
ans = max(ans, min(d1[c], d2[c]))
print(ans)

1 Like