Overview

This problem can be viewed by applying run-length encoding (decomposing the string into blocks of identical characters) and efficiently counting the number of intervals whose compressed sequence becomes ABA.
For each character block (run) treated as the middle, if the blocks on the left and right are the same character, we add the number of combinations to the answer.

Analysis

First, the condition that the compressed sequence of interval \([l,r]\) has length \(3\) with the 1st and 3rd characters being the same is equivalent to:

• The compressed sequence is exactly of the form A B A (\(A \ne B\)).

---

Naively trying all intervals gives \(O(N^2)\) intervals, and constructing the compressed sequence for each takes additional time, so for \(N \le 10^6\) this is far too slow.

The key observation is as follows.

Apply run-length encoding to string \(S\) to obtain:

• chars = [character of each run]
• lens = [length of each run]

For example, AAABBBAA gives chars=[A,B,A], lens=[3,3,2].

A sandwich interval has compressed sequence ABA, so it spans exactly 3 consecutive runs in the run-length encoding.
That is, for some middle run \(k\):

• Left run: \(k-1\)
• Middle run: \(k\)
• Right run: \(k+1\)

These 3 runs are used, and additionally chars[k-1] == chars[k+1] must hold.

The number of ways to choose such an interval is:

• Number of choices for the starting position within the left run: lens[k-1] (it can start anywhere within the run)
• Number of choices for the ending position within the right run: lens[k+1] (it can end anywhere within the run)

The middle run must be entirely included (this ensures the 2nd character of the compressed sequence is formed).
Therefore, the number of sandwich intervals created by this middle run \(k\) is

\[ \text{lens}[k-1] \times \text{lens}[k+1] \]

We sum this over all \(k=1,\dots,m-2\) (where \(m\) is the number of runs).

Algorithm

1. Scan string \(S\) from the beginning, apply run-length encoding, and construct chars and lens.
2. Let the number of runs be \(m\). If \(m<3\), the answer is \(0\).
3. For each \(k=1\) to \(m-2\):
   • If chars[k-1] == chars[k+1], then
     ans += lens[k-1] * lens[k+1]
4. Output ans.

Complexity

• Time complexity: \(O(N)\)
  (Run-length encoding takes \(O(N)\), and the subsequent scan takes \(O(m)\le O(N)\))
• Space complexity: \(O(N)\)
  (In the worst case where all characters are different, the number of runs is \(m=N\))

Implementation Notes

• Run-length encoding can be implemented efficiently and concisely using a while loop to find the end of each block of identical characters.

• The answer can be very large, but Python’s int supports arbitrary precision, so it can be handled directly.

• Returning early when \(m<3\) makes the code clearer and safer.

  Source Code

import sys

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

    # Run-length encoding: chars and lengths
    chars = []
    lens = []
    i = 0
    while i < N:
        j = i + 1
        c = S[i]
        while j < N and S[j] == c:
            j += 1
        chars.append(c)
        lens.append(j - i)
        i = j

    m = len(chars)
    if m < 3:
        print(0)
        return

    ans = 0
    # For each middle run b, need pattern a b a with adjacent runs
    for k in range(1, m - 1):
        if chars[k - 1] == chars[k + 1]:
            ans += lens[k - 1] * lens[k + 1]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.