solution1（通过40%）
依次求子串并统计出现过的字母个数
#include<iostream>
#include<string>
#include<set>
using namespace std;
int main(){string s, subs;cin >> s;int len = s.size(), ans = 0;for(int j = 1; j <= len; j++){for(int i = 0; i < len; i++){if(i + j > len) break;set<char> set1;subs = s.substr(i, j);//cout << subs << endl;for(int i = 0; i < subs.size(); i++){set1.insert(subs[i]);}ans += set1.size();}}printf("%d", ans);return 0;
}
solution1.2(通过50%)
#include<iostream>
#include<string>
using namespace std;
int main(){string s, subs;cin >> s;int len = s.size(), ans = 0;for(int j = 1; j <= len; j++){for(int i = 0; i < len; i++){if(i + j > len) break;int flag[24] = {0};subs = s.substr(i, j);for(int i = 0; i < subs.size(); i++){if(!flag[subs[i] - 'a']){ans++;flag[subs[i] - 'a']++;}}}}printf("%d", ans);return 0;
}
solution2递推
每位上的字母的贡献为从最左首次不出现到，到字符串末尾
例如ababc里第二个位置上的b
左边未出现过b的子串为 : ，a
右边从当前到末尾的子串可能有 , a, ab, abc
则第二个位置的b贡献为24 = (2 - 0)(5 - 2 + 1)//这里加上是该字母单独为子串的情况，即子串b
#include<iostream>
#include<string>
using namespace std;
int main(){string s;cin >> s;int pre[25] = {0};long long len = s.size(), ans = 0;//有两个测试点结果超出intfor(int i = 1; i <= len; i++){ans += (i - pre[s[i - 1] - 'a']) * (len - i + 1);pre[s[i - 1] - 'a'] = i;}printf("%lld", ans);return 0;
}
