AcWing 2872. 子串分值和
原题链接
中等
作者:
fxzcloud
,
2021-01-15 20:42:25
,
所有人可见
,
阅读 1352
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
long len = s.length();
char[] ch = new char[(int)len+5];
for(int i=1;i<=len;i++) ch[i] = s.charAt(i-1);
long res = 0;
int[] pre = new int[30];
for(int i=1;i<=len;i++){
res += (i-pre[ch[i]-'a'])*(len-i+1);
pre[ch[i]-'a'] = i;
}
System.out.println(res);
}
}
/*
pre[ch[i]-'a']之前的没有判断的意义了
*/
/*
a个数 x b个数
必须包含x的字串有(a+1)*(b+1)个
*/
大佬能解释下 res += (i-pre[ch[i]-‘a’])*(len-i+1);这是怎么来的么
就是类似“左边两条路右边三条路一共有6种走法”,同理,对于此刻枚举的第i的字符来说,从其前一次出现的位置+1到此刻i都是其可能开始的地方;而从此刻i到结尾则可能是其结束的地方。比如,ababc对应下标01234,对于第二个a来说,下标[x,y]x的取值范围是[1,2],Y则是[1,4]。这样一来的话左边可选有2,右边可选有4,相乘为8;对每一个字符都用这样的思路去思考,最终就是O(n)复杂度的解
很强
感谢大佬回答