LeetCode 2207. 字符串中最多数目的子字符串
题目链接:
【分析】由于pattern中只有两个字符,假设分别是a、b,只需要统计出text中每个a后面有多少b即可,这儿这个通过后缀和的思想,先算出总的b的个数,如果当前字符是a,那么后面b的个数就是总的b的个数,如果是b,就把总的b的个数-1。由于最后还可以插入一个a或者b,显然插在两端的时候会使总的个数增加最多。如果在前面插入a,则这个a可以和总的b组成pattern,总个数增大b;如果在后面插入b,则这个b可以组成a个pattern,所以最后在答案加一个a和b总数的最大值即可。
另外对于a==b的情况来说,假设aaaa,那么可以组成aa的情况有3+2+1种,最后再+4即a的总个数,用等差数列求和公式即可,但是一定要注意算乘法的时候先转long,否则会溢出。
class Solution { public long maximumSubsequenceCount(String text, String pattern) { char a = pattern.charAt(0), b = pattern.charAt(1); int n = text.length(), i; int x = 0, y = 0, t = 0; long ans = 0; char c; if(a == b){ for(i = 0; i < n; i++){ if(text.charAt(i) == a) x++; } return (long)(x + 1) * x / 2; } for(i = 0; i < n; i++) { if(text.charAt(i) == a) x++; else if(text.charAt(i) == b) y++; } int m = y; for(i = 0; i < n; i++){ if(text.charAt(i) == a) ans += y; else if(text.charAt(i) == b) y--; } return ans + Math.max(x, m); } }