解题思路

核心想法（双指针 + 最近位置）

把 26 个大写字母之间的“矛盾关系”看作一个无向图的边。对一个右端点固定的子串，若它是“和谐”的，则右端点字符不能与窗口内任何与其矛盾的字母同时出现。

用滑动窗口（双指针）从左到右扫描：

1. 预处理一个 conflict[26][26] 的布尔矩阵，conflict[a][b]=conflict[b][a]=true 表示字母 a 与 b 互相矛盾。
2. 维护每个字母在当前扫描位置之前的最近出现位置 last[26]，初始化为 -1。

本题为2025年9月13日滴滴机考原题

滴滴机考的介绍点击这里

题目内容

小钟有一个长度为 $n$ 的全部由大写英文字母组成的字符用 $s$ 。然而，这 $26$ 个英文字母之间并不总是和谐相处的，

有 $m$ 对字母之间存在矛盾,分别表示为 $\left(c h_{1,1}, c h_{1,2}\right),\left(c h_{2,1}, c h_{2,2}\right), \ldots,\left(c h_{m, 1}, c h_{m, 2}\right)$ 。

对于某字符用 $t$ ，当且仅当任意两个字符之间不存在矛盾，则称该字符是和谐的。

小钟想问你，$s$ 的所有连续非空子串中，有多少子串是和谐的?

注意，两个子串不同，当且仅当两个子串在字符串中出现的位置不同。

例如，对于字符串 $s=AAAA，S_{1,2}=AA$ 与 $s_{2,3}=AA$ 视为不同的子串。

输入描述

第一行有两个整数 $n(1≤n≤2*10^5)$ 、$m(0≤m≤500)$ ，分别表示字符串 $s$ 的长度和存在矛盾的字符对的个数。

第二行有一行字符串 $s$ 。

接下来 $m$ 行第 $i$ 行有两个字符 $ch_{i,1}、ch_{i,2}$ ，表示字符 $ch_{i,1}$ 与字符 $ch_{i,2}$ 之间存在矛盾。

保证任何字符不会与自己产生矛盾。矛盾关系可能出现重复。

输出描述

输出一个数字，表示 $s$ 的多少连续子串是和谐的。

样例1

输入

4 1
ACBA
A B

输出

6

说明

样例中一共有 $10$ 个子串：$A、C、B、A、AC、CB、BA、ACB、CBA、ACBA$ ，其中共有 $6$ 个子串满足不同时出现 $A$ 和 $B$ 。