1717. 删除子字符串的最大得分Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

删除子字符串 "ab" 并得到 x 分。
- 比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
删除子字符串"ba" 并得到 y 分。
- 比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
  总得分为 5 + 4 + 5 + 5 = 19 。

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4 输出：20

提示：

1 <= s.length <=10⁵
1 <= x, y <= 104
s 只包含小写英文字母。

# 思路

两个栈模拟，先删除得分大的再删除小的

# 解法

class Solution {
    public int maximumGain(String s, int x, int y) {
    	char ta='a';
    	char tb='b';
    	if(x>y) {
    		x^=y;y^=x;x^=y;
            ta^=tb;tb^=ta; ta^=tb;
    	}
    	int ans=0;
        char[]c=s.toCharArray();
        Deque<Character>deque=new ArrayDeque<>();
        Deque<Character>deque2=new ArrayDeque<>();
        for(int i=0;i<c.length;i++) {
        	char t=c[i];
        	if(t==ta) {
        		if(!deque.isEmpty()&&deque.peek()==tb) {
        			deque.pop();
        			ans+=y;
        			continue;
        		}
        	}
        	deque.push(t);
        }
        while(!deque.isEmpty()) {
        	char t=deque.pollLast();
        	if(t==tb) {
        		if(!deque2.isEmpty()&&deque2.peek()==ta) {
        			deque2.pop();
        			ans+=x;
        			continue;
        		}
        	}
        	deque2.push(t);
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 总结

分析出几种情况，然后分别对各个情况实现

#Java