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 removeAdjacentDuplicateChar

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() < 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 < 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);
    }
}

StackExchange Code Review Q#133729, answer score: 5