CF1748B Diverse Substrings

一个非空数字字符串被称为“多样的”，如果其中每个字符出现的次数都不超过该字符串中不同字符的个数。 例如： - 字符串 "7" 是多样的，因为 $7$ 出现了 $1$ 次，而不同字符的个数也是 $1$。 - 字符串 "77" 不是多样的，因为 $7$ 出现了 $2$ 次，而不同字符的个数只有 $1$。 - 字符串 "1010" 是多样的，因为 $0$ 和 $1$ 都出现了 $2$ 次，而不同字符的个数是 $2$。 - 字符串 "6668" 不是多样的，因为 $6$ 出现了 $3$ 次，而不同字符的个数是 $2$。 给定一个长度为 $n$ 的字符串 $s$，该字符串只包含数字 $0$ 到 $9$。请你计算它的 $ \frac{n(n+1)}{2} $ 个子串中有多少个是多样的。 如果字符串 $a$ 可以通过从字符串 $b$ 的开头和结尾各删除若干（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的一个子串。 注意，如果同一个多样的字符串在 $s$ 中出现多次，每次出现都要单独计数。例如，在字符串 "77" 中有两个多样的子串 "7"，所以该字符串的答案是 $2$。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示字符串 $s$ 的长度。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 的所有字符都是 $0$ 到 $9$ 的数字。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示给定字符串 $s$ 的多样子串的数量。

在第一个测试用例中，多样子串为 "7"。 在第二个测试用例中，唯一的多样子串是 "7"，它出现了两次，所以答案是 $2$。 在第三个测试用例中，多样子串有 "0"（出现 $2$ 次）、"01"、"010"、"1"（出现 $2$ 次）、"10"（出现 $2$ 次）、"101" 和 "1010"。 在第四个测试用例中，多样子串有 "0"（出现 $3$ 次）、"01"、"011"、"0110"、"1"（出现 $2$ 次）、"10"、"100"、"110" 和 "1100"。 在第五个测试用例中，多样子串有 "3"、"39"、"399"、"6"、"9"（出现 $4$ 次）、"96" 和 "996"。 在第六个测试用例中，字符串 "23456" 的所有 $15$ 个非空子串都是多样的。 由 ChatGPT 4.1 翻译