Minimum Substring Length (Editorial)

Idea

Let us write the positions of all G characters in the string into a separate array $p$. Let the number of such positions be $m$. Since we write the positions from left to right, the array $p$ is already sorted.

We need to choose $k$ characters G that are contained in the shortest possible segment. In the optimal answer, these $k$ characters will be consecutive in the array $p$. Therefore, it is sufficient to iterate over all groups of $k$ consecutive elements.

For a group

the shortest segment containing all these characters starts at p_i and ends at p_{i+k-1}. Therefore, its length is determined as

Thus, the answer is

The overall time complexity is — $O(n)$.