Overview

Given a string \(S\), the problem asks to count the number of contiguous substrings whose compressed sequence has length exactly 3 and whose 1st and 3rd characters are equal (sandwich intervals). This can be efficiently counted using run-length encoding.

Analysis

Focus on the relationship between compressed sequences and “runs”

First, apply Run-Length Encoding (RLE) to the string \(S\). Consider the sequence of “runs,” where consecutive identical characters are grouped together.

Example: AABBA → Run sequence: \((A, 2),\ (B, 2),\ (A, 1)\)

A key observation here is that the compressed sequence of a substring is simply the characters of the runs that the substring spans, listed in order.

Reformulating the sandwich interval condition

For the compressed sequence to have length exactly 3, the substring must span exactly 3 consecutive runs. Specifically, it is a substring that starts somewhere in run \(i\) and ends somewhere in run \(i+2\) (fully containing run \(i+1\)).

In this case, the compressed sequence is \([\text{runs}[i].\text{char},\ \text{runs}[i+1].\text{char},\ \text{runs}[i+2].\text{char}]\), and the condition that the 1st and 3rd characters are equal is:

\[\text{runs}[i].\text{char} = \text{runs}[i+2].\text{char}\]

Comparison with the naive approach

Exhaustively checking all \((l, r)\) pairs requires \(O(N^2)\) combinations, which is too slow for \(N \le 10^6\). However, by using run-length encoding, we can solve the problem in \(O(m)\) (where \(m \le N\)) with respect to the number of runs \(m\).

Algorithm

1. Apply run-length encoding to the string \(S\) to obtain the run sequence \(\text{runs}[0], \text{runs}[1], \dots, \text{runs}[m-1]\). Each run is a pair of (character, length).

2. For each triplet of consecutive runs \((\text{runs}[i],\ \text{runs}[i+1],\ \text{runs}[i+2])\), if \(\text{runs}[i].\text{char} = \text{runs}[i+2].\text{char}\), then the number of ways to choose the starting position is \(\text{runs}[i].\text{len}\) and the number of ways to choose the ending position is \(\text{runs}[i+2].\text{len}\), so add their product to the answer.

Concrete example: The run sequence of AABBA is \((A,2), (B,2), (A,1)\)

• \(i=0\): \(A = A\), so add \(2 \times 1 = 2\)
• Sandwich intervals: \([1,5]\) (AABBA → ABA) and \([2,5]\) (ABBA → ABA)

Complexity

• Time complexity: \(O(N)\) (\(O(N)\) for run-length encoding, \(O(m) \le O(N)\) for scanning the run sequence)
• Space complexity: \(O(N)\) (for storing the run sequence)

Implementation Notes

• Run-length encoding can be easily implemented by advancing a pointer as long as the same character continues from the beginning.

• The answer can be as large as the sum of products of run lengths, which can become very large when \(N = 10^6\), so 64-bit integers are required (in Python, arbitrary-precision integers are used automatically, so this is not a concern).

• Note that if \(N < 3\) or the number of runs is less than 3, the answer is 0.

  Source Code

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    S = data[1].decode()
    
    if N < 3:
        print(0)
        return
    
    # Compute run-length encoding
    runs = []
    i = 0
    while i < N:
        j = i
        while j < N and S[j] == S[i]:
            j += 1
        runs.append((S[i], j - i))
        i = j
    
    m = len(runs)
    ans = 0
    for i in range(m - 2):
        if runs[i][0] == runs[i + 2][0]:
            ans += runs[i][1] * runs[i + 2][1]
    
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.