Interval Composition

Time limit1sMemory limit256 MB

Summary

Find the maximum length L such that each of the two lowercase strings has a contiguous block of length L with the same letter counts.

Level: Medium6 of 10
Topics: Prefix sum, Hash map, String
Solved: No attempts yet

Problem

Two devices A and B each emit one signal per second. The signals a device emitted form a sequence of lowercase letters in time order. For example, let the signal sequences $S_A$ and $S_B$ be the following.

$S_A$ = [a, f, c, d, r, d, e, s, d, e, f, w, s, z, r]
$S_B$ = [g, e, d, s, r, d, d, e, m, z, r]

An interval is a contiguous part of a sequence. Two intervals have the same composition when they hold the same letters with the same multiplicities, in any order. The two boxed intervals in the picture below have the same composition. The 4th letter through the 10th letter of $S_A$ , which is d, r, d, e, s, d, e, and the 2nd letter through the 8th letter of $S_B$ , which is e, d, s, r, d, d, e, both consist of three d, two e, one r and one s.

Two intervals with the same composition always have the same length. More than one such pair of intervals can exist. Find the longest pair of intervals with the same composition, one in each of the two signal sequences.

Input

The first line and the second line each hold one signal sequence as a string with no spaces. Both strings consist of lowercase English letters only. The lengths $N$ and $M$ of the two strings satisfy $1 \le N, M \le 1500$ .

Output

Print on the first line the length of the longest pair of intervals with the same composition. If no such pair exists, print $0$ .

Examples3

Example 1
Input
```
xraphy
edgeedgem
```
Expected output
```
0
```
Example 2
Input
```
afcdrdesdefwszr
gedsrddemzr
```
Expected output
```
7
```
Example 3
Input
```
computersystem
sesystuercomplexity
```
Expected output
```
11
```