PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
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)