Another Wine Tasting Event
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: combinatorics, constructive algorithms, math, strings

After the first successful edition, Gabriella has been asked to organize a second wine tasting event. There will be $$$2n - 1$$$ bottles of wine arranged in a row, each of which is either red wine or white wine.

This time, Gabriella has already chosen the type and order of all the bottles. The types of the wines are represented by a string $$$s$$$ of length $$$2n - 1$$$. For each $$$1 \le i \le 2n - 1$$$, it holds that $$$s_i = \texttt{R}$$$ if the $$$i$$$-th bottle is red wine, and $$$s_i = \texttt{W}$$$ if the $$$i$$$-th bottle is white wine.

Exactly $$$n$$$ critics have been invited to attend. The critics are numbered from $$$1$$$ to $$$n$$$. Just like last year, each critic $$$j$$$ wants to taste an interval of wines, that is, the bottles at positions $$$a_j, \, a_j + 1, \, \dots, \, b_j$$$ for some $$$1 \le a_j \le b_j \le 2n - 1$$$. Moreover, they have the following additional requirements:

- each of them wants to taste at least $$$n$$$ wines, that is, it must hold that $$$b_j - a_j + 1 \ge n$$$;
- no two critics must taste exactly the same wines, that is, if $$$j \ne k$$$ it must hold that $$$a_j \ne a_k$$$ or $$$b_j \ne b_k$$$.

Gabriella knows that, since the event is held in a coastal region of Italy, critics are especially interested in the white wines, and don't care much about the red ones. (Indeed, white wine is perfect to accompany seafood.) Thus, to ensure fairness, she would like that all critics taste the same number of white wines.

Help Gabriella find an integer $$$x$$$ (with $$$0 \le x \le 2n - 1$$$) such that there exists a valid assignment of intervals to critics where each critic tastes exactly $$$x$$$ white wines. It can be proved that at least one such $$$x$$$ always exists.

Input format:
The first line contains the integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — where $$$2n - 1$$$ is the number of bottles, and $$$n$$$ is the number of critics.

The second line contains a string $$$s$$$ of length $$$2n - 1$$$ that represents the arrangement of the wines — the $$$i$$$-th character of $$$s$$$ ($$$1 \le i \le 2n - 1$$$) is $$$\texttt{R}$$$ for a red wine and $$$\texttt{W}$$$ for a white wine.

Output format:
Print an integer $$$x$$$ — the number of white wines that each critic will taste.

It can be proved that at least one solution exists. If multiple solutions exist, any of them will be accepted.

Constraints:
Time limit: 0.5 s
Memory limit: 256.0 MB

Note:
In the first sample, there are $$$5$$$ critics and $$$2 \cdot 5 - 1 = 9$$$ bottles of wine. A possible set of intervals that makes each critic taste $$$2$$$ white wines is the following: $$$[2, 6],$$$ $$$[1, 6],$$$ $$$[4, 8],$$$ $$$[1, 5],$$$ $$$[3, 7]$$$. Note that all intervals contain at least $$$5$$$ bottles.

In the second sample, there is $$$1$$$ critic and $$$2 \cdot 1 - 1 = 1$$$ bottle of wine. The only possible interval is $$$[1, 1]$$$, which gives $$$x = 0$$$.

Example input:
5
RWWRRRWWW

Example output:
2

Example input:
1
R

Example output:
0

Editorial:
For an interval $$$[l, r]$$$ ($$$1 \le l \le r \le 2n - 1$$$), let $$$w(l, r)$$$ be the number of $$$\texttt{W}$$$'s in the substring $$$s_l \dots s_r$$$.
We are going to show that $$$x = \max_{1 \le l \le n} w(l, \, l + n - 1)$$$ is a solution (that is, there are at least $$$n$$$ intervals of length $$$\ge n$$$ containing exactly $$$x$$$ $$$\texttt{W}$$$'s).
Let $$$k$$$ be an index such that $$$w(k, \, k + n - 1) = x$$$. The idea is to find $$$n - 1$$$ other intervals with the same number of $$$\texttt{W}$$$'s by "sliding" the original interval $$$[k, \, k + n - 1]$$$ in a clever way.
For each $$$l=1, \, 2, \, \dots, \, k-1$$$, let $$$L_l$$$ be the shortest interval starting at $$$l$$$ with $$$w(L_l)=x$$$. Such interval exists because $$$w(l, \, k+n-1)\ge w(k, \, k+n-1) = x$$$ and moreover the length of $$$L_l$$$ cannot be smaller than $$$n$$$ by definition of $$$x$$$. Similarly, for each $$$r=k+n, k+n+1, \dots, 2n-1$$$, let $$$R_r$$$ be the shortest interval ending at $$$r$$$ with $$$w(R_r)=x$$$.
We have constructed a family of $$$n$$$ intervals: $$$L_1, \, L_2, \, \dots, \, L_{k-1}, \, [k, \, k+n-1], \, R_{k+n}, \, R_{k+n+1}, \, \dots, \, R_{2n-1}$$$. All of them have length $$$\ge n$$$ and all of them contain exactly $$$x$$$ $$$\texttt{W}$$$'s. Are they all distinct? Clearly $$$L_i \ne L_j$$$ and $$$R_i \ne R_j$$$ whenever $$$i \ne j$$$. Moreover, $$$[k, \, k+n-1]$$$ is different from all the other intervals. Could it be that $$$L_l=R_r$$$? No, because that would mean that such interval is $$$[l, r]$$$ with $$$l<k$$$ and $$$k+n-1<r$$$, but then $$$[k, \, k+n-1]$$$ would be strictly contained inside $$$[l, r]$$$, violating the minimality of $$$L_l$$$ and $$$R_r$$$.