leetcode 1047. Remove All Adjacent Duplicates In String（删除相邻的重复字母）

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Example 1:

Input: s = “abbaca”
Output: “ca”
Explanation:
For example, in “abbaca” we could remove “bb” since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is “aaca”, of which only “aa” is possible, so the final string is “ca”.

和1544题如出一辙，都是删除相邻的重复字母，从左到右只删除相邻的2个。

思路：

和1544题一样，从左到右遍历，用stack保存字母，
遇到相同的字母出栈(pop)，否则压栈(push)。

这里用一个数组模拟stack，更高效。

public String removeDuplicates(String s) {
    int n = s.length();
    char[] st = new char[n];
    char[] arr = s.toCharArray();
    
    int top = -1;
    
    for(char ch : arr) {
        if(top >= 0 && ch == st[top]) {
            top --;
        } else {
            st[++top] = ch; 
        }
    }
    return String.copyValueOf(st, 0, top+1); //最后一个参数是offset, 也就是substring的长度，top是0为起点的，所以要+1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16