概要

この問題は、文字列を連長圧縮（同じ文字の塊に分解）して見ると、「圧縮列が ABA になる区間」を効率よく数える問題です。
各文字の塊（run）を真ん中にして、左右の塊が同じ文字なら、その組み合わせ数を足し上げれば答えになります。

考察

まず、区間 \([l,r]\) の圧縮列が長さ \(3\) で、1文字目と3文字目が同じという条件は、

• 圧縮列がちょうど A B A（\(A \ne B\)）の形

であることと同じです。

---

素朴に全区間を試すと、区間数は \(O(N^2)\) 個あり、各区間で圧縮列を作るとさらに時間がかかるため、\(N \le 10^6\) では到底間に合いません。

ここで重要な観察は次です。

文字列 \(S\) を連長圧縮して、

• chars = [各runの文字]
• lens = [各runの長さ]

とします。
たとえば AAABBBAA なら chars=[A,B,A], lens=[3,3,2] です。

サンドイッチ区間は、圧縮列が ABA なので、連長圧縮後の run をちょうど3個またぐ区間になります。
つまり、ある中央 run を \(k\) として、

• 左 run: \(k-1\)
• 中央 run: \(k\)
• 右 run: \(k+1\)

の3つを使い、さらに chars[k-1] == chars[k+1] が必要です。

このとき区間の取り方は：

• 左 run からの開始位置の選び方：lens[k-1] 通り（run内のどこから始めてもよい）
• 右 run での終了位置の選び方：lens[k+1] 通り（run内のどこで終わってもよい）

中央 run は必ず丸ごと通る必要があります（これで圧縮列の2文字目が成立）。
よって、この中央 \(k\) が作るサンドイッチ区間数は

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

です。これを全ての \(k=1,\dots,m-2\)（\(m\) はrun数）で合計すればよいです。

アルゴリズム

1. 文字列 \(S\) を先頭から見て連長圧縮し、chars, lens を作る。
2. run数を \(m\) とする。\(m<3\) なら答えは \(0\)。
3. 各 \(k=1\) から \(m-2\) について：
   • もし chars[k-1] == chars[k+1] なら
     ans += lens[k-1] * lens[k+1]
4. ans を出力。

計算量

• 時間計算量: \(O(N)\)
  （連長圧縮が \(O(N)\)、その後の走査が \(O(m)\le O(N)\)）
• 空間計算量: \(O(N)\)
  （最悪で全て文字が異なると run 数 \(m=N\)）

実装のポイント

• 連長圧縮は while で「同じ文字が続く区間の終端」を探す実装にすると高速で書きやすいです。

• 答えは大きくなる可能性がありますが、Python の int は多倍長なのでそのまま扱えます。

• m<3 のとき早期 return すると分かりやすく安全です。

  ソースコード

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

---

この解説は gpt-5.3-codex によって生成されました。