/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
AtCoder 国には「トラック運転手は A 分以上運転する際には B 分以上の休憩を取らなければならない」というルールがあります。
a, b からなる長さ N の文字列 S と正整数 A,B が与えられます。以下の条件を全て満たす整数組 (l,r) の個数を求めてください。
- 1\leq l \leq r \leq N
- S の l 文字目から r 文字目までに含まれる
aの個数が A 以上 - S の l 文字目から r 文字目までに含まれる
bの個数が B 未満
制約
- 1\leq N \leq 3\times 10^5
- 1 \leq A,B \leq N
- S は
a,bのみからなる長さ N の文字列 - 与えられる数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B S
出力
答えを出力せよ。
入力例 1
11 4 2 abbaaabaaba
出力例 1
3
条件を満たす (l,r) の組は (4,8),(4,9),(5,9) の 3 個です。
入力例 2
13 1 2 bbbbbbbbbbbbb
出力例 2
0
条件を満たす (l,r) の組は存在しません。
Score : 300 points
Problem Statement
In AtCoder Country, there is a rule that "a truck driver must take a break of at least B minutes when driving for A minutes or more."
You are given a string S of length N consisting of a and b, and positive integers A and B. Find the number of integer pairs (l,r) that satisfy all of the following conditions.
- 1\leq l \leq r \leq N
- The number of
ain the substring from the l-th character through the r-th character of S is greater than or equal to A. - The number of
bin the substring from the l-th character through the r-th character of S is less than B.
Constraints
- 1\leq N \leq 3\times 10^5
- 1 \leq A,B \leq N
- S is a string of length N consisting of
aandb. - All input numbers are integers.
Input
The input is given from Standard Input in the following format:
N A B S
Output
Print the answer.
Sample Input 1
11 4 2 abbaaabaaba
Sample Output 1
3
The pairs (l,r) that satisfy the conditions are (4,8),(4,9),(5,9), which is three pairs.
Sample Input 2
13 1 2 bbbbbbbbbbbbb
Sample Output 2
0
There are no pairs (l,r) that satisfy the conditions.