C - Comfortable Distance 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。

整数の組 (i, j) であって、以下の条件をすべて満たすものの個数を求めてください。

  • 1 \leq i \leq j \leq N
  • S_i = S_j
  • L \leq j - i \leq R

制約

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq L \leq R \leq N - 1
  • N, L, R は整数
  • S は長さ N の英小文字からなる文字列

入力

入力は以下の形式で標準入力から与えられる。

N L R
S

出力

答えを出力せよ。

入力例 1

6 2 4
aabcba

出力例 1

2

問題文中の条件をすべて満たす整数の組は (i, j) = (2, 6), (3, 5) の 2 つです。

入力例 2

9 3 6
aaaaaaaaa

出力例 2

18

入力例 3

10 2 6
aabbccaabb

出力例 3

6

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the number of pairs of integers (i, j) satisfying all of the following conditions:

  • 1 \leq i \leq j \leq N
  • S_i = S_j
  • L \leq j - i \leq R

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq L \leq R \leq N - 1
  • N, L, R are integers.
  • S is a string of length N consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

N L R
S

Output

Output the answer.

Sample Input 1

6 2 4
aabcba

Sample Output 1

2

The pairs of integers satisfying all the conditions in the problem statement are (i, j) = (2, 6), (3, 5), for a total of two pairs.

Sample Input 2

9 3 6
aaaaaaaaa

Sample Output 2

18

Sample Input 3

10 2 6
aabbccaabb

Sample Output 3

6