Given a string S of lowercase 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 is guaranteed the answer is unique.

Example 1:

Input: "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".

Note:

1. 1 <= S.length <= 20000
2. S consists only of English lowercase letters.

删除字符串中的所有相邻重复项。题目不难理解，就是请你删除字符串中有相邻字母的部分。根据例子的解释，不难想到需要用stack处理。遍历input字符串，判断当前遍历到的字符是否和栈顶字符一样，若一样，就把栈顶元素pop出来，同时当前字符也就略过不处理了。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public String removeDuplicates(String S) {
 3         // corner case
 4         if (S == null || S.length() == 0) {
 5             return S;
 6         }
 7 
 8         // normal case
 9         Deque<Character> stack = new ArrayDeque<>();
10         for (Character c : S.toCharArray()) {
11             if (stack.isEmpty()) {
12                 stack.push(c);
13             } else if (c == stack.peekLast()) {
14                 stack.pollLast();
15             } else {
16                 stack.add(c);
17             }
18         }
19 
20         StringBuilder sb = new StringBuilder();
21         while (!stack.isEmpty()) {
22             sb.append(stack.pollFirst());
23         }
24         return sb.toString();
25     }
26 }

 

相关题目

1047. Remove All Adjacent Duplicates In String

1209. Remove All Adjacent Duplicates in String II

LeetCode 题目总结