LeetCode 2207. 字符串中最多数目的子字符串

本文主要是介绍LeetCode 2207. 字符串中最多数目的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

力扣https://leetcode-cn.com/problems/maximize-number-of-subsequences-in-a-string/

【分析】由于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);}
}

 

 

这篇关于LeetCode 2207. 字符串中最多数目的子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---