小乐乐与字符串【Java版】

思路

• 暴力枚举超时。
• 抓住“CHN”字符串只有三个字符这个特点。
• 统计C的数量countC
• 每遇到一个H字符，就能构成countC数量的CH串，countCH += countC
• 每遇到一个N字符，就能构成countCH数量的CHN串，所以ans += countCH
• 最后的结果就是ans

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        /*统计子串*/
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String ss = "CHN";
        long countC = 0;
        long  countCH = 0;
        long ans = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i)=='C') countC++;
            if(s.charAt(i)=='H') countCH+=countC; //遇到H就可以组成countC个CH
            if(s.charAt(i)=='N') ans += countCH; //遇到N就可以组成countCH个CHN
        }
        System.out.println(ans);
    }
}