概要

文字列 \(S\) のすべての連続部分文字列について、圧縮列の長さがちょうど 3 かつ 1 文字目と 3 文字目が等しい区間（サンドイッチ区間）の個数を求める問題です。ランレングス圧縮を用いることで効率的に数え上げられます。

考察

圧縮列と「ラン」の関係に注目する

まず、文字列 \(S\) をランレングス圧縮（RLE） します。同じ文字の連続をひとまとめにした「ラン」の列を考えます。

例: AABBA → ラン列: \((A, 2),\ (B, 2),\ (A, 1)\)

ここで重要な観察として、部分文字列の圧縮列は、その部分文字列がまたがるランの文字を順に並べたものになります。

サンドイッチ区間の条件を言い換える

圧縮列の長さがちょうど 3 になるためには、部分文字列がちょうど 連続する 3 つのラン にまたがる必要があります。具体的には、ラン \(i\) のどこかから始まり、ラン \(i+2\) のどこかで終わる部分文字列です（ラン \(i+1\) は完全に含む）。

このとき圧縮列は \([\text{runs}[i].\text{char},\ \text{runs}[i+1].\text{char},\ \text{runs}[i+2].\text{char}]\) となり、1 文字目と 3 文字目が等しい条件は：

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

素朴なアプローチとの比較

すべての \((l, r)\) の組を全探索すると \(O(N^2)\) 通りあり、\(N \le 10^6\) では間に合いません。しかしランレングス圧縮を使えば、ラン数 \(m\) に対して \(O(m)\)（\(m \le N\)）で解けます。

アルゴリズム

1. 文字列 \(S\) をランレングス圧縮し、ラン列 \(\text{runs}[0], \text{runs}[1], \dots, \text{runs}[m-1]\) を得る。各ランは（文字, 長さ）の組。

2. 連続する 3 つのラン \((\text{runs}[i],\ \text{runs}[i+1],\ \text{runs}[i+2])\) について、\(\text{runs}[i].\text{char} = \text{runs}[i+2].\text{char}\) ならば、開始位置の選び方が \(\text{runs}[i].\text{len}\) 通り、終了位置の選び方が \(\text{runs}[i+2].\text{len}\) 通りなので、その積を答えに加算する。

具体例: AABBA のラン列は \((A,2), (B,2), (A,1)\)

• \(i=0\): \(A = A\) なので \(2 \times 1 = 2\) を加算
• サンドイッチ区間: \([1,5]\)（AABBA→ABA）と \([2,5]\)（ABBA→ABA）

計算量

• 時間計算量: \(O(N)\)（ランレングス圧縮に \(O(N)\)、ラン列の走査に \(O(m) \le O(N)\)）
• 空間計算量: \(O(N)\)（ラン列の格納）

実装のポイント

• ランレングス圧縮は、先頭から同じ文字が続く限りポインタを進めるだけで簡単に実装できます。

• 答えの値は最大で各ランの長さの積の総和となり、\(N = 10^6\) の場合に非常に大きくなる可能性があるため、64 ビット整数が必要です（Python では自動で多倍長整数になるため心配不要）。

• \(N < 3\) やラン数が 3 未満の場合は答えが 0 になる点に注意します。

  ソースコード

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()

---

この解説は claude4.6opus-thinking によって生成されました。