删除子字符串的最大得分
难度:
标签:
题目描述
代码结果
运行时间: 167 ms, 内存: 16.4 MB
/*
* 思路:
* 1. 使用Java Stream简化操作流程。
* 2. 分别处理'ab'和'ba'的删除过程,优先删除得分高的组合。
* 3. 使用Java Stream进行字符串操作时可以使用StringBuilder。
*/
import java.util.stream.Stream;
import java.util.Stack;
public class SolutionStream {
public int maximumGain(String s, int x, int y) {
int score = 0;
if (x >= y) {
score += process(s, "ab", x);
score += process(s, "ba", y);
} else {
score += process(s, "ba", y);
score += process(s, "ab", x);
}
return score;
}
private int process(String s, String pattern, int score) {
StringBuilder sb = new StringBuilder();
int totalScore = 0;
for (char c : s.toCharArray()) {
sb.append(c);
if (sb.length() >= 2 && sb.substring(sb.length() - 2).equals(pattern)) {
sb.setLength(sb.length() - 2);
totalScore += score;
}
}
return totalScore;
}
}
解释
方法:
这个解法主要通过一次遍历来优先删除得分更高的子字符串。首先,通过比较x和y的大小来决定优先删除哪种子字符串('ab'或'ba')。如果x >= y,则优先删除'ab';反之,优先删除'ba'。遍历字符串s的每一个字符,用cnt_a和cnt_b分别记录当前未匹配的'a'和'b'的数量。当遇到'b'时,如果x >= y并且之前有未匹配的'a',则删除'ab'并累加得分x;否则,增加'b'的计数。当遇到'a'时,如果y > x并且之前有未匹配的'b',则删除'ba'并累加得分y;否则,增加'a'的计数。如果遇到非'a'或'b'的字符,此时检查并处理剩余的'a'和'b',能组成多少对就删除多少对,并根据x和y的较小值累加得分。通过这种方法,可以在一次遍历中处理所有可能的得分并达到最大化。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在分析删除子字符串'ab'和'ba'的得分时,仅考虑了当前字符与前一个字符的匹配,而没有考虑后续可能出现的更优的匹配序列?
▷🦆
在实现中,添加了一个结尾标志'-'以便处理最后一组字符。这种处理方式是否可能影响字符串中原有的计数逻辑?比如,如果原字符串以'a'或'b'结尾,这种处理是否会导致最后一个字符被错误地忽略或错误计数?
▷🦆
算法中提到,如果遇到非'a'或'b'的字符,则会处理剩余的'a'和'b'。请问这种处理方式是否总是有效,还是只适用于特定的情况?例如,如果字符串结束时有大量未匹配的'a'和'b',这种简单的处理是否足够有效?
▷🦆
在代码中,每遇到一个非'a'或'b'字符时,就会重置'a'和'b'的计数器。这种重置操作是否可能导致在某些情况下错过删除某些子字符串的机会?例如,如果字符串中'a'和'b'的分布是间断的,这种处理方式是否会影响最终的得分?
▷