Remove All Adjacent Duplicates In String

LeetCode Q 1047 - Remove All Adjacent Duplicates In String

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 <= S.length <= 20000
• S consists only of English lowercase letters.

Solution

Version 1: Using Stack

public String removeDuplicates(String S) {
  if (S == null || S.length() == 0)
    return S;
  
  Stack<Character> stack = new Stack<>();
  
  for (char ch: S.toCharArray()) {
    if(!stack.empty() && stack.peek() == ch)
      stack.pop();
    else
      stack.push(ch);
  }
  
  StringBuilder sb = new StringBuilder();
  while (!stack.empty())
    sb.append(stack.pop());
  
  return sb.reverse().toString();
}

Version 2: Using Deque, much faster

public String removeDuplicates(String S) {
  if (S == null || S.length() == 0)
    return S;

  Deque<Character> dq = new ArrayDeque<>();
  for (char ch: S.toCharArray()) {
	if (!dq.isEmpty() && dq.peekLast() == ch) {
		dq.pollLast();
	} else {
		dq.offer(ch);
	}
  }

  StringBuilder sb = new StringBuilder();
  for (char ch: dq)
  	sb.append(ch);

  return sb.toString();
}

Why should we use Deque over Stack?

In JavaDoc for Deque syas:
Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.

• Stack extends Vector which means it is synchronized for each operation. If we don’t want synchronized operation, using stack always let code run more slowly than using deque.

• Deque is more consistent. Deque exposes a set of operations which is all about being able to fetch/add/remove items from the start or thee end of a collection, iterate etc.

• Stack has no interface, so if you know you need Stack operations you end up committing to a specific concrete class, which isn’t usually a good idea.

Equivalent Queue Method in Deque

The Deque interface extends Queue interface. When a deque is used as a queue, FIFO behavior results. Elements are added at the end of the deque and reomved from the beginning.

Queue Method	Euqivalent Deque Method	Queue Method	Euqivalent Deque Method
add(e)	addLast(e)	remove(e)	removeFirst(e)
offer(e)	offerLast(e)	poll(e)	pollFirst(e)
element(e)	getFirst(e)	poll(e)	pollFirst(e)

Equivalent Stack Method in Deque

The Deque can also be used as LIFO stacks. This interface should be used in preference to the lagacy Stack class. When a deque is used as a stack, elements are pushed and poped from the beginning of the deque.

Stack Method	Euqivalent Stack Method	Stack Method	Euqivalent Stack Method
push(e)	addFirst(e)	pop(e)	removeFirst(e)
peek(e)	peekFirst(e)

method iterator() in Deque
Iterator<E> iterator()
Returns an iterator over the elements in this deque in proper sequeence. The elements will be returned in order from first(head) to last (tail).
Therefore, Stack and Deque have reverse iteration orders:

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3

Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1