题解

我们可以用一种新型的记录方法，也可以记录到所有的子串.

例如 $abcadcb$：

遍历到第 $1$ 个字符，$l=1,r=1$：将 $a$ 加入字符串，并增加 $1$ 个子串： $a$.

遍历到第 $2$ 个字符，$l=1,r=2$：将 $b$ 加入字符串，并增加 $2$ 个子串：$b,ab$.

遍历到第 $3$ 个字符，$l=1,r=3$：将 $c$ 加入字符串，并增加 $3$ 个子串：$c,bc,abc$.

遍历到第 $4$ 个字符，$r=4$：由于已经出现过了 $a$，所以第 $1$ 个字符就不能要了，令 $l=2$. 此时可新增 $3$ 个子串：$a,ca,bca$.

遍历到第 $5$ 个字符，$l=2,r=5$：将 $d$ 加入字符串，并增加 $4$ 个子串：$d,ad,cad,bcad$.

遍历到第 $6$ 个字符，$r=6$：由于已经出现过了 $c$，所以第 $2,3$ 个字符就不能要了，令 $l=4$. 此时可新增 $3$ 个子串：$c,dc,adc$​.

遍历到第 $7$ 个字符，$l=4,r=7$：将 $b$ 加入字符串，并增加 $4$ 个子串：$b,cb,dcb,adcb$.

$\therefore$ 共有 $20$ 个不含有重复字符的子串.

翻译成代码如下：

#include <iostream>
#include <cstdio>
#include <set>
#define int long long
using namespace std;
int a[100005];
set <char> vis;//当时赶时间，用了set，如果用bool数组可以降到严格O(n)
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	string s;
	cin >> s;
	int ct = 0, l = 0;
	for(int i = 0; i < s.length(); i++){
		while(vis.find(s[i]) != vis.end()){//找到重复元素
			vis.erase(s[l++]);//前面的字符不能要了
		}
		vis.insert(s[i]);
		ct += i - l + 1;//加入这些状态
	}
	cout << ct;

	return 0;
}

时间复杂度：$O(|S|)$