P15146 [SWERC 2025] LFS

You are designing the new videogame Live Fight Simulator. A level is defined by a string $s$ of length $n$ consisting of lowercase English letters, where each letter represents a type of enemy that appears in sequence. To analyze the gameplay balance, you need to measure how repetitive different parts of the level are. You will consider $q$ specific contiguous segments $s[l, r]$ of the level, with $1 \le l \le r \le n$. For each of these queries, you want to compute the length of the LFS (Longest Frequent Substring). Formally, for any string $t$: - let $f(t)$ be the maximum frequency of any substring in $t$; - let $|\text{LFS}(t)|$ be the maximum length of a substring of $t$ that appears exactly $f(t)$ times. For each query $(l, r)$, you must compute $|\text{LFS}(s[l, r])|$, which represents the maximum length among the most repetitive patterns of enemy spawns in that part of the level. A string $x$ is a substring of a string $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

The first line contains two integers $n, q$ ($1 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^5$) — the length of the sequence and the number of level segments to analyze. The second line contains a string $s$ of length $n$ consisting of lowercase English letters. Each of the next $q$ lines contains two integers $l, r$ ($1 \le l \le r \le n$), representing a query on the substring $s[l, r]$.

Print $q$ lines. The $i$-th line must contain a single integer: the value of $|\text{LFS}(s[l, r])|$ for the pair $(l, r)$.

#### Explanation of sample 1. In the first example: - In the first query, the substring is $t = s[1, 1] = \text{"a"}$. The maximum frequency of a substring inside $\text{"a"}$ is 1, reached by $\text{"a"}$ itself, whose length is 1. Therefore, the answer is 1. - In the second query, the substring is $t = s[1, 5] = \text{"ababa"}$. The maximum frequency of a substring inside $\text{"ababa"}$ is 3, reached by $\text{"a"}$, whose length is 1. Therefore, the answer is 1. - In the third query, the substring is $t = s[1, 4] = \text{"abab"}$. The maximum frequency of a substring inside $\text{"abab"}$ is 2, reached by $\text{"a"}$, $\text{"b"}$ and $\text{"ab"}$. Among these strings, the one with maximum length is $\text{"ab"}$, whose length is 2. Therefore, the answer is 2. - In the fourth query, the substring is $t = s[2, 5] = \text{"baba"}$. The maximum frequency of a substring inside $\text{"baba"}$ is 2, reached by $\text{"a"}$, $\text{"b"}$ and $\text{"ba"}$. Among these strings, the one with maximum length is $\text{"ba"}$, whose length is 2. Therefore, the answer is 2.