给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入：“abbaca” 输出：“ca” 解释： 例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：
1 <= S.length <= 20000 S 仅由小写英文字母组成。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法一：直接法
public String removeDuplicates(String S) { StringBuilder sb = new StringBuilder(); int n = S.length(); int i = 0; char[] chars = S.toCharArray();//使用chars比直接读S.charAt(i)效率更高 while (i < n) { if (i + 1 < n && chars[i] == chars[i + 1]) { i += 2; continue; } int sbLength = sb.length(); if (sbLength > 0 && sb.charAt(sbLength - 1) == chars[i]) { sb.deleteCharAt(sbLength - 1); i++; continue; } sb.append(chars[i]); i++; } return sb.toString(); }法二：用栈，但实际上没啥必要，因为法一里隐含的就是一个栈的逻辑
public String removeDuplicates_2(String S) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < S.length(); i++) { char c = S.charAt(i); if (stack.isEmpty()) { stack.add(c); continue; } if (stack.peek() == c) { stack.pop(); continue; } stack.add(c); } StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { char c = stack.pop(); sb.append(c); } sb.reverse(); return sb.toString(); }法三：直接根据题意的模拟
public String removeDuplicates_3(String S) { StringBuilder sb = new StringBuilder(S); while (true) { int size = sb.length(); for (int i = 0; i < size - 1; i++) { if (sb.charAt(i) != sb.charAt(i + 1)) { continue; } else { sb.delete(i, i + 2); break; } } if (sb.length() == size) { break; } } return sb.toString(); }