public class Solution {

  public String deDup(String input) {

    // Write your solution here

    char[] charArr = input.toCharArray();

    LinkedList<Character> stack = new LinkedList<>();

    for (int i = 0; i < charArr.length; i++) {

      char cur = charArr[i];

      if (!stack.isEmpty() && stack.peekFirst() == cur) {

        while (i + 1 < charArr.length && charArr[i] == charArr[i + 1]) {

          i += 1;

        }

        stack.pollFirst();

      } else {

        stack.offerFirst(cur);

      }

    }

    char[] res = new char[stack.size()];

    for (int i = res.length - 1; i >= 0; i--) {

      res[i] = stack.pollFirst();

    }

    return new String(res);

  }

}