leetcode
leetcode 1501 ~ 1550
删除子字符串的最大得分

删除子字符串的最大得分

难度:

标签:

题目描述

代码结果

运行时间: 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'的字符时,都对之前累积的'a'和'b'进行结算,以清空计数器。这意味着每个非'a'或'b'的字符都像一个分割点,强制算法结算前面的子字符串。如果字符串结束时有大量未匹配的'a'和'b',这种方法仍然有效,因为结尾标志'-'将触发最后一次必要的结算。
🦆
在代码中,每遇到一个非'a'或'b'字符时,就会重置'a'和'b'的计数器。这种重置操作是否可能导致在某些情况下错过删除某些子字符串的机会?例如,如果字符串中'a'和'b'的分布是间断的,这种处理方式是否会影响最终的得分?
虽然重置操作可能看似会错过某些删除机会,但在这种实现中,每次遇到非'a'或'b'的字符时,重置前都会尝试将当前累积的'a'和'b'尽可能匹配并删除,这保证了在每个分段内部'a'和'b'都得到了有效处理。因此,即使'a'和'b'的分布是间断的,每段内部的处理仍然尽可能地优化得分,不会因为重置操作而错过删除子字符串的机会。这种方法保持了算法的高效性和简洁性。

相关问题