题解

题面描述

给定一个长度为 $n$ 的字符串 $s$，仅由小写字母组成。定义两个不同的位置 $i$ 和 $j$ 是“有缘分的”，如果它们对应的字符 $s_i$ 和 $s_j$ 在字母表中的位置差（即相隔的字母个数）不超过 $g$。具体来说，字母表的第 $1$ 个字母是 'a'，第 $26$ 个字母是 'z'。两个字符的位置差是它们在字母表中相隔的字母个数。例如，'a' 和 'd' 的位置差是 $2$（因为中间隔了 'b' 和 'c'）。

解题思路

题目内容

对于给定的长度为$n$，仅由小写字母组成的字符串$S_1S_2···S_n$。如果有这样的两个不同的位置$i$和$j$，满足其上的字符 $S_i$和 $S_j$在字母表中相差的位置数小于等于$g$，那么我们称$i$和$j$是“有缘分的”。

你需要求解，对于给定的$g$，字符串$s$中，有多少对位置是“有缘分的”。

字母表的第$1$个字母为‘$a$’，第$26$个字母为‘$z$’。两个字符在字母表中的位置差，即为它们在字母表中相隔的字母个数。

例如，'$a$’与‘$d$’之间隔了‘$b$’和‘$c$’两个字母，所以位置差为$2$。

输入描述

第一行输入两个整数$n, g (1 ≦n≤10^3; 0≦g≦25)$代表字符串的长度、约束。

第二行输入一个长度为$n$，仅由小写字母组成的字符串$s$。

输出描述

输出一个整数，代表满足条件的“有缘分的”位置对数。

样例1

输入

3 25
aaa

输出

3

说明

在这个样例中，一共有三对不同的位置分别是$(1,2)、(1,3)$和$(2,3)$，每一对位置上的字符在字母表中相差的位置数都恰为$0$，所以均满足条件。

样例2

输入

4 1
acbd

输出

5