概要

文字列を「同じ文字の連続区間」にまとめて見ると、サンドイッチ区間はちょうど 3 個の連続する塊 をまたぐ区間に対応します。
したがって、まずランレングス圧縮を行い、その後 A-B-A の形になっている 3 連続の塊ごとに個数を数えれば、線形時間で解けます。

考察

まず、文字列 \(S\) を同じ文字ごとの連続区間に分解して考えます。

たとえば

• AAABBBAA → A(3), B(3), A(2)
• ABBCCCCAA → A(1), B(2), C(4), A(2)

のように、
文字の種類を chars、その長さを lens として持つことにします。

---

重要な観察 1: 部分文字列の圧縮列は「またいだ塊の列」になる

元の文字列を

\(S = c_1^{L_1} c_2^{L_2} \dots c_m^{L_m}\)

と表します。ここで

• \(c_i\) は各塊の文字
• \(L_i\) はその塊の長さ
• 隣り合う塊では必ず \(c_i \ne c_{i+1}\)

です。

ある部分文字列が、塊 \(i\) から塊 \(j\) までをまたぐとします。
このとき、その部分文字列の圧縮列はちょうど

\(c_i c_{i+1} \dots c_j\)

になります。

なぜなら、

• 各塊の中は同じ文字なので、圧縮すると 1 文字になる
• 隣り合う塊は必ず異なる文字なので、圧縮で消えない

からです。

---

重要な観察 2: サンドイッチ区間は「ちょうど 3 つの連続する塊」をまたぐ

サンドイッチ区間の条件は、

• 圧縮列の長さがちょうど \(3\)
• 1 文字目と 3 文字目が等しい

でした。

つまり圧縮列は必ず

ABA

の形です。

これは、部分文字列が ちょうど 3 個の連続する塊 をまたいでいて、その文字が

\(c_i, c_{i+1}, c_{i+2}\)

となり、さらに

\(c_i = c_{i+2}\)

を満たすことと同値です。

---

重要な観察 3: 個数は両端の選び方だけで決まる

3 つの連続する塊

\(c_i^{L_i}, c_{i+1}^{L_{i+1}}, c_{i+2}^{L_{i+2}}\)

があり、\(c_i = c_{i+2}\) だとします。

この 3 塊をまたぐサンドイッチ区間を作るには、

• 左端を 1 つ目の塊のどこかから選ぶ：\(L_i\) 通り
• 右端を 3 つ目の塊のどこかから選ぶ：\(L_{i+2}\) 通り

とすればよいです。

真ん中の塊は、連続部分文字列である以上必ず全部含まれます。

したがって、この 3 塊から作れるサンドイッチ区間の個数は

\(L_i \times L_{i+2}\)

個です。

---

例

AAABBBAA を考えます。

これは塊にすると

• A(3), B(3), A(2)

です。

文字列の並びは A-B-A なので条件を満たします。
よって個数は

\(3 \times 2 = 6\)

個です。

実際、左端は最初の A の 3 か所、右端は最後の A の 2 か所から選べます。

---

素朴な方法がだめな理由

すべての区間 \([l, r]\) を調べると、区間数は \(O(N^2)\) 個あります。
さらに各区間について圧縮列を作るともっと重くなり、\(N \le 10^6\) では到底間に合いません。

そこで、

• 文字列全体を先に塊に圧縮する
• 3 連続の塊だけを見る

ことで、全体を \(1\) 回なめるだけで答えを求めます。

アルゴリズム

1. 文字列 \(S\) を左から見て、ランレングス圧縮を行う。

   • 各塊の文字を chars
   • 各塊の長さを lens に保存する。

2. 圧縮後の塊数を \(m\) とする。

3. 各 \(i = 0, 1, \dots, m-3\) について、

   • もし chars[i] == chars[i+2] なら
     • lens[i] * lens[i+2] を答えに加える

4. 最後に答えを出力する。

---

数式で書くと、答えは

\(\displaystyle \sum_{i=1}^{m-2} [c_i = c_{i+2}] \cdot L_i \cdot L_{i+2}\)

です。
ここで \([P]\) は、条件 \(P\) が真なら \(1\)、偽なら \(0\) を表します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

※ 塊の数は最大でも \(N\) 個です。

実装のポイント

• ランレングス圧縮は 1 回の走査で作れます。

• 答えは大きくなる可能性があるので、Python 以外では long long などの 64bit 整数を使うのが安全です。

• chars[i] == chars[i+2] のときだけ lens[i] * lens[i+2] を加える、という非常にシンプルな実装で済みます。

  ソースコード

import sys

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

    chars = []
    lens = []

    prev = S[0]
    cnt = 1
    for ch in S[1:]:
        if ch == prev:
            cnt += 1
        else:
            chars.append(prev)
            lens.append(cnt)
            prev = ch
            cnt = 1
    chars.append(prev)
    lens.append(cnt)

    ans = 0
    m = len(chars)
    for i in range(m - 2):
        if chars[i] == chars[i + 2]:
            ans += lens[i] * lens[i + 2]

    print(ans)

if __name__ == "__main__":
    main()

---

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