Overview

This problem asks you to count the number of contiguous substrings of a given string \(S\) whose “compressed sequence” has length \(3\) and whose 1st and 3rd characters match.

Analysis

Properties of the Compressed Sequence and the “Sandwich Interval” Condition

The compressed sequence of a string is obtained by collapsing each run of consecutive identical characters into a single character. For example, the compressed sequence of AAABBAAAA is ABA.

Organizing the “sandwich interval” condition from the problem statement, the compressed sequence of a contiguous substring \(S[l..r]\) must have the form \(X_1 X_2 X_3\), with \(X_1 = X_3\). This means the substring has the following structure:

1. Character \(A\) repeated \(1\) or more times (Block 1)
2. Character \(B\) (\(B \neq A\)) repeated \(1\) or more times (Block 2)
3. Character \(A\) repeated \(1\) or more times (Block 3)

Moreover, for the compressed sequence length to be exactly \(3\), the chosen range \([l, r]\) must span exactly \(3\) distinct character blocks, even if there are other characters immediately before or after the substring.

Efficient Counting

Since \(N\) can be up to \(10^6\), brute-forcing all intervals \((l, r)\) would take \(O(N^2)\), which is too slow. Instead, we divide the string into “blocks” of consecutive identical characters (run-length encoding).

For example, AAABBBAA is divided into the following \(3\) blocks: - Block 0: A repeated \(3\) times - Block 1: B repeated \(3\) times - Block 2: A repeated \(2\) times

Here, the intervals \([l, r]\) whose compressed sequence is ABA are exactly those that “start at some position within Block 0, include all of Block 1, and end at some position within Block 2.”

In general, for three consecutive blocks \(i, i+1, i+2\), if the character of block \(i\) and the character of block \(i+2\) are the same, then every \((l, r)\) satisfying the following conditions is a sandwich interval: - \(l\) can be any position within block \(i\). - \(r\) can be any position within block \(i+2\).

In this case, if the length of block \(i\) is \(L_i\) and the length of block \(i+2\) is \(L_{i+2}\), the number of such combinations is \(L_i \times L_{i+2}\).

Algorithm

1. Run-Length Encoding: Scan the string \(S\) and convert runs of consecutive identical characters into a list of “character” and “length” pairs. Example: AAABBBAA \(\rightarrow\) [('A', 3), ('B', 3), ('A', 2)]
2. Triplet Check: Iterate through the list of compressed blocks from the beginning. For each three consecutive blocks \((i, i+1, i+2)\), check whether block[i].character == block[i+2].character.
3. Count Addition: If the condition is satisfied, add block[i].length * block[i+2].length to the answer.
4. Output the Result: Output the final total.

Complexity

• Time Complexity: \(O(N)\) Scanning the string once to build the blocks takes \(O(N)\), and scanning the list of blocks (at most \(N\) blocks) once takes \(O(N)\), so the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\) Memory is needed to store the run-length encoded data.

Implementation Notes

• Since the string length \(N\) can be large, in Python it is advisable to read input efficiently using methods such as sys.stdin.read().split().

• Adjacent blocks always consist of different characters, so when block[i].character == block[i+2].character holds, it is automatically guaranteed that the middle block[i+1] has a different character.

  Source Code

import sys

def solve():
    # Read all input from standard input at once
    input_data = sys.stdin.read().split()
    if len(input_data) < 2:
        return
    
    # The first element is N, the length of the string
    n = int(input_data[0])
    
    # The string S may be split across multiple lines in some input formats,
    # so we join all subsequent elements to form the complete string.
    # For N=10^6, this is efficient enough in Python.
    s = "".join(input_data[1:])
    
    # Update n to be the actual length of the string s
    n = len(s)
    
    # A sandwich interval must have a compressed sequence of length exactly 3.
    # This requires the substring to span at least 3 characters.
    if n < 3:
        print(0)
        return

    # To find all sandwich intervals, we first compress the string into blocks
    # of identical consecutive characters. Each block is represented by its
    # character and its length.
    chars = []
    lengths = []
    
    if n > 0:
        curr_char = s[0]
        curr_len = 0
        for char in s:
            if char == curr_char:
                curr_len += 1
            else:
                chars.append(curr_char)
                lengths.append(curr_len)
                curr_char = char
                curr_len = 1
        # Add the final block
        chars.append(curr_char)
        lengths.append(curr_len)
    
    num_blocks = len(chars)
    ans = 0
    
    # A sandwich interval corresponds to a sequence of exactly three consecutive
    # blocks (B_i, B_{i+1}, B_{i+2}) such that the character in the first block
    # is the same as the character in the third block (chars[i] == chars[i+2]).
    #
    # Because adjacent blocks always have different characters, if chars[i] == chars[i+2],
    # the character in the middle block (chars[i+1]) must be different.
    # Thus, the compressed sequence for any substring starting in block i,
    # covering all of block i+1, and ending in block i+2 will be
    # (chars[i], chars[i+1], chars[i]). This sequence has length exactly 3
    # and its 1st and 3rd characters are equal.
    #
    # The number of such intervals for a specific triple of blocks is the
    # number of ways to choose a starting position in the first block (lengths[i])
    # multiplied by the number of ways to choose an ending position in the
    # third block (lengths[i+2]).
    for i in range(num_blocks - 2):
        if chars[i] == chars[i+2]:
            ans += lengths[i] * lengths[i+2]
            
    # Output the total count of sandwich intervals
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.