time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Let's denote the f(x)????(????) function for a string x???? as the number of distinct characters that the string contains. For example f(abc)=3????(abc)=3, f(bbbbb)=1????(bbbbb)=1, and f(babacaba)=3????(babacaba)=3.
Given a string s????, split it into two non-empty strings a???? and b???? such that f(a)+f(b)????(????)+????(????) is the maximum possible. In other words, find the maximum possible value of f(a)+f(b)????(????)+????(????) such that a+b=s????+????=???? (the concatenation of string a???? and string b???? is equal to string s????).
Input
The input consists of multiple test cases. The first line contains an integer t???? (1≤t≤1041≤????≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer n???? (2≤n≤2⋅1052≤????≤2⋅105) — the length of the string s????.
The second line contains the string s????, consisting of lowercase English letters.
It is guaranteed that the sum of n???? over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case, output a single integer — the maximum possible value of f(a)+f(b)????(????)+????(????) such that a+b=s????+????=????.
Example
input
Copy
5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz
output
Copy
2 7 2 10 3
Note
For the first test case, there is only one valid way to split aaaa into two non-empty strings aa and aa, and f(a)+f(a)=1+1=2????(a)+????(a)=1+1=2.
For the second test case, by splitting abcabcdabcabcd into abcabc and abcdabcd we can get the answer of f(abc)+f(abcd)=3+4=7????(abc)+????(abcd)=3+4=7 which is maximum possible.
For the third test case, it doesn't matter how we split the string, the answer will always be 22.
解题说明：此题是求两个集合的最大值，每个集合中只统计不同数字的个数。可以采用C++里面的vector和set，vector属于顺序容器，其元素与存储位置与操作操作有关；set属于关联容器，其元素相当于键值。 set能够保证它里面所有的元素都是不重复的。于是遍历数组，求出最大的情况即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
string s;
cin >> s;
vector<int>v(n);
set<char>a;
for (int i = n - 1; i >= 0; i--)
{
a.insert(s[i]);
v[i] = a.size();
}
a.clear();
int r = 0;
for (int i = 0; i < n - 1; i++)
{
a.insert(s[i]);
r = max(r, (int(a.size()) + v[i + 1]));
}
cout << r << endl;
}
return 0;
}