Problem

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.

Examples

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

Example 2:

Input:
s = "azxxzy"
Output:
 "ay"

Solution

Method 1 - Using Stack 🏆

Code

Java
public String removeDuplicates(String S) {
	Stack<Character> stack = new Stack<>();
	for (char c : S.toCharArray()) {
		if (!stack.isEmpty() && stack.peek() == c) {
			stack.pop();
		} else {
			stack.push(c);
		}
	}
	StringBuilder sb = new StringBuilder();
	stack.forEach(sb::append);
	return sb.toString();
}

We can also use StringBuilder as stack:

public String removeDuplicates(String S) {
	StringBuilder sb = new StringBuilder();
	for (char c : S.toCharArray()) {
		int size = sb.length();
		if (size > 0 && sb.charAt(size - 1) == c) {
			sb.deleteCharAt(size - 1);
		} else {
			sb.append(c);
		}
	}
	return sb.toString();
}

OR using Array Deque:

public String removeDuplicates(String S) {
	Deque<Character> dq = new ArrayDeque<>();
	for (char c : S.toCharArray()) {
		if (!dq.isEmpty() && dq.peekLast() == c) { 
			dq.pollLast();
		}else {
			dq.offer(c);
		}
	}
	StringBuilder sb = new StringBuilder();
	for (char c : dq) { sb.append(c); }
	return sb.toString();
}

Method 2 - Two Pointers

If current char is same as the end of non-adjacent-duplicate chars, decrease the counter end by 1; otherwise, copy the current char to its end.

Code

Java
public String removeDuplicates(String S) {
	char[] a = S.toCharArray();
	int end = -1;
	for (char c : a) {
		if (end >= 0 && a[end] == c) { 
			--end; 
		}else { 
			a[++end] = c; 
		}
	}
	return String.valueOf(a, 0, end + 1);
}