Overview

If we view the string by grouping it into “consecutive runs of the same character,” a sandwich interval corresponds exactly to an interval that spans 3 consecutive runs.
Therefore, we first perform run-length encoding, and then for every 3 consecutive runs forming an A-B-A pattern, we count the number of valid intervals. This solves the problem in linear time.

Analysis

First, let’s decompose the string \(S\) into consecutive runs of the same character.

For example:

• AAABBBAA → A(3), B(3), A(2)
• ABBCCCCAA → A(1), B(2), C(4), A(2)

We store the character type of each run in chars and its length in lens.

---

Key Observation 1: The compressed sequence of a substring corresponds to the sequence of runs it spans

We represent the original string as

\(S = c_1^{L_1} c_2^{L_2} \dots c_m^{L_m}\)

where:

• \(c_i\) is the character of each run
• \(L_i\) is the length of that run
• Adjacent runs always satisfy \(c_i \ne c_{i+1}\)

Suppose a substring spans from run \(i\) to run \(j\).
Then the compressed sequence of that substring is exactly

\(c_i c_{i+1} \dots c_j\)

This is because:

• Within each run, all characters are the same, so compression reduces it to 1 character
• Adjacent runs always have different characters, so they are not merged during compression

---

Key Observation 2: A sandwich interval spans “exactly 3 consecutive runs”

The conditions for a sandwich interval are:

• The compressed sequence has length exactly \(3\)
• The 1st and 3rd characters are equal

In other words, the compressed sequence must be of the form

ABA

This is equivalent to the substring spanning exactly 3 consecutive runs with characters

\(c_i, c_{i+1}, c_{i+2}\)

and satisfying

\(c_i = c_{i+2}\)

---

Key Observation 3: The count depends only on the choices for the two endpoints

Consider 3 consecutive runs

\(c_i^{L_i}, c_{i+1}^{L_{i+1}}, c_{i+2}^{L_{i+2}}\)

where \(c_i = c_{i+2}\).

To form a sandwich interval spanning these 3 runs:

• Choose the left endpoint from somewhere in the 1st run: \(L_i\) choices
• Choose the right endpoint from somewhere in the 3rd run: \(L_{i+2}\) choices

The middle run is necessarily included in its entirety, since the substring must be contiguous.

Therefore, the number of sandwich intervals formed from these 3 runs is

\(L_i \times L_{i+2}\)

---

Example

Consider AAABBBAA.

Grouping into runs gives:

• A(3), B(3), A(2)

The character sequence is A-B-A, which satisfies the condition.
Thus the count is

\(3 \times 2 = 6\)

Indeed, the left endpoint can be chosen from 3 positions in the first A run, and the right endpoint from 2 positions in the last A run.

---

Why a naive approach doesn’t work

Examining all intervals \([l, r]\) gives \(O(N^2)\) intervals.
Additionally, computing the compressed sequence for each interval makes it even heavier, which is far too slow for \(N \le 10^6\).

Instead, by:

• Compressing the entire string into runs first
• Only examining 3 consecutive runs

we can compute the answer in a single pass over the data.

Algorithm

1. Scan the string \(S\) from left to right and perform run-length encoding.

   • Store the character of each run in chars
   • Store the length of each run in lens

2. Let \(m\) be the number of runs after compression.

3. For each \(i = 0, 1, \dots, m-3\):

   • If chars[i] == chars[i+2], then
     • Add lens[i] * lens[i+2] to the answer

4. Output the final answer.

---

Written as a formula, the answer is

\(\displaystyle \sum_{i=1}^{m-2} [c_i = c_{i+2}] \cdot L_i \cdot L_{i+2}\)

where \([P]\) equals \(1\) if condition \(P\) is true, and \(0\) otherwise.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

※ The number of runs is at most \(N\).

Implementation Notes

• Run-length encoding can be constructed in a single scan.

• The answer can become large, so in languages other than Python, it is safe to use 64-bit integers such as long long.

• The implementation is very simple: just add lens[i] * lens[i+2] only when chars[i] == chars[i+2].

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()

    chars = []
    lens = []

    prev = S[0]
    cnt = 1
    for ch in S[1:]:
        if ch == prev:
            cnt += 1
        else:
            chars.append(prev)
            lens.append(cnt)
            prev = ch
            cnt = 1
    chars.append(prev)
    lens.append(cnt)

    ans = 0
    m = len(chars)
    for i in range(m - 2):
        if chars[i] == chars[i + 2]:
            ans += lens[i] * lens[i + 2]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.