MINLCS - Editorial

editorial
,
1

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)
1 Like