问题 5851 --可爱的字符串

5851: 可爱的字符串★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 17
[提交][状态][命题人:]

题目描述

      定义:给定一个非空的数字字符串(字符串中的字符都为数字字符),如果该字符串中的任意一个字符的出现次数都不超过字符串中的不同字符的个数,则称该字符串为可爱的字符串。
      比如:
    (1)“7”是可爱字符串,因为7在字符串中出现1次,该字符串中不同字符的个数也为1.
    (2)“77”不是一个可爱字符串,因为7在字符串中出现2次,该字符串中不同字符的个数为1.
    (3)“1010”是一个可爱字符串,因为0或1在字符串中出现次数都为2,该字符串中不同字符个数也为2.
    (4)“6668”不是一个可爱字符串,因为6在字符串中出现了3次,而字符串中不同字符的个数为2.
      现给我们一个由数字字符组成的长度为n的字符串s,请计算在其(n*(n-1))/2个子串中,有多少个是可爱字符串。

输入

    第一行一个整数t (1≤t≤10000):测试用例的数量。
    每个测试用例的第一行一个整数n (1≤n≤10^5): 字符串s的长度.
    每个测试用例的第二行包含一个长度为n的字符串s,每个字符串都只由‘0’到‘9’这些数字字符组成。
    测试数据确保所有字符串长度之和不超过10^5.

输出

    对于每个测试用例,输出一个整数 :字符串s中的可爱子字符串的数量。
样例输入
Copy
7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798
样例输出
Copy
1
2
10
12
10
15
106

提示

来源

 

[提交][状态]