Remove adjacent duplicate characters Introduction

This problem is essentially equivalent to this HackerRank problem.

The task is to remove all duplicate characters that are adjacent to each other in a given String, until no adjacent characters are the same. If a String only contains adjacent duplicate characters then return an empty String.

Examples:


baab => bb => "" (return an empty String)
aabcd => bcd


Implementation

The core implementation logic uses Stacks to do most of the work.


Translate the input String to a Stack made up of Characters
Create a new Stack that will contain the non-duplicate Characters which will be outputted
pop through the input Stack


If the output Stack is empty, add the character
If the first element of the output Stack is the same Character as the popped Character then
pop the output Stack because this indicates that the two adjacent Characters are duplicate
Else
push the popped input Stack element to the output Stack



Feedback

I'm looking for general feedback as I'm still pretty green to Java. So if I have some serious design pattern issues, or if I'm missing something very obvious, I'd love to get feedback around that.

A couple thoughts on my mind:


Initially I tried implementing logic that iterated through Lists which worked but isn't as efficient as this implementation. One thing that I do like about this implementation is that it identifies the duplicate characters in one iteration, which you could achieve through Lists, I think, but the logic is more intuitive when using Stacks (I think).
Naming


I think the name AdjacentDuplicateCharactersRemover is relatively appropriate, but what are good names for the underlying methods? I struggled with this for a while because they are both doing similar things (removing / filtering characters).



Actual Implementation



public class AdjacentDuplicateCharactersRemover {

  public static String removeAdjacentDuplicateCharacters(final String candidate) {
    if (candidate.length() &lt; 2) {
      return candidate;
    }

    final Stack&lt;Character&gt; originalCharacters = new Stack&lt;&gt;();
    for (char c : candidate.toCharArray()) {
      originalCharacters.push(c);
    }
    final Stack&lt;Character&gt; filteredCharacters = AdjacentDuplicateCharactersRemover.filterAdjacentDuplicateCharacters(originalCharacters);
    final StringBuilder stringBuilder = new StringBuilder();
    while (!filteredCharacters.empty()) {
      stringBuilder.append(filteredCharacters.pop());
    }
    return stringBuilder.toString();
  }

  public static Stack&lt;Character&gt; filterAdjacentDuplicateCharacters(final Stack&lt;Character&gt; characters) {
    if (characters.size() &lt; 2) {
      return characters;
    }

    final Stack&lt;Character&gt; filteredCharacters = new Stack&lt;&gt;();
    while (!characters.empty()) {
      final char poppedChar = characters.pop();
      if (filteredCharacters.empty() || poppedChar != filteredCharacters.peek()) {
        filteredCharacters.push(poppedChar);
      } else {
        filteredCharacters.pop();
      }
    }

    return filteredCharacters;
  }
}
The naming of the class is OK, I think.  It could be better named AdjacentSameCharacterPairsRemover. "Same" is shorter than "duplicate". "Pairs" corrects a misunderstanding that I initially had, which was that "aaa" → "" instead of "aaa" → "a".  The name still wouldn't convey the idea that the elimination is applied repeatedly, but there's only so much information that you can fit into a name.

I don't think that the function name needs to be that long, if the class name is already descriptive.  The parameter name, candidate, is peculiar.  What office is that string running for, or what validation are you performing on it?

I don't recommend marking parameters and local variables as final — it just adds visual clutter.  Functions should be short enough that you can easily keep track of all the variables in your head simultaneously.

You don't need the special case for if (candidate.length() &lt; 2); the algorithm works just fine without it.  The added complexity isn't worth the potential performance benefit.

I would work directly with the char[] and dispense with the Stack and StringBuilder.  By doing so, you would eliminate the need for extra storage, the boxing of chars as Characters, the synchronized behaviour of java.util.Stack, and the semi-deprecated status of java.util.Stack.  You also would't need to push all of the original characters onto the stack and then filter it, since the character array is the input.  You wouldn't need to translate the Stack back to a StringBuilder to make the String.  The code would be simplified so much that you could eliminate the helper function altogether.

public class AdjacentSameCharacterPairsRemover {
    // Suppress the default constructor
    private AdjacentSameCharacterPairsRemover() {}

    public static String process(String s) {
        char[] chars = s.toCharArray();
        int len = 0;      // Length of result (initially empty)

        for (int i = 0; i &lt; chars.length; i++) {
            if (len == 0 || chars[i] != chars[len - 1]) {
                chars[len++] = chars[i];   // Push one char onto "stack"
            } else {
                len--;                     // Pop one char from "stack"
            }
        }
        return new String(chars, 0, len);
    }
}