我们可以用一种新型的记录方法,也可以记录到所有的子串.
例如 abcadcbabcadcbabcadcb:
遍历到第 111 个字符,l=1,r=1l=1,r=1l=1,r=1:将 aaa 加入字符串,并增加 111 个子串: aaa.
遍历到第 222 个字符,l=1,r=2l=1,r=2l=1,r=2:将 bbb 加入字符串,并增加 222 个子串:b,abb,abb,ab.
遍历到第 333 个字符,l=1,r=3l=1,r=3l=1,r=3:将 ccc 加入字符串,并增加 333 个子串:c,bc,abcc,bc,abcc,bc,abc.
遍历到第 444 个字符,r=4r=4r=4:由于已经出现过了 aaa,所以第 111 个字符就不能要了,令 l=2l=2l=2. 此时可新增 333 个子串:a,ca,bcaa,ca,bcaa,ca,bca.
遍历到第 555 个字符,l=2,r=5l=2,r=5l=2,r=5:将 ddd 加入字符串,并增加 444 个子串:d,ad,cad,bcadd,ad,cad,bcadd,ad,cad,bcad.
遍历到第 666 个字符,r=6r=6r=6:由于已经出现过了 ccc,所以第 2,32,32,3 个字符就不能要了,令 l=4l=4l=4. 此时可新增 333 个子串:c,dc,adcc,dc,adcc,dc,adc .
遍历到第 777 个字符,l=4,r=7l=4,r=7l=4,r=7:将 bbb 加入字符串,并增加 444 个子串:b,cb,dcb,adcbb,cb,dcb,adcbb,cb,dcb,adcb.
∴\therefore∴ 共有 202020 个不含有重复字符的子串.
翻译成代码如下:
时间复杂度:O(∣S∣)O(|S|)O(∣S∣)