# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Jeevan Jyot Singh

*Tejas Pandey, Hriday*

**Testers:***Nishank Suresh*

**Editorialist:**# 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)
```