Replacing consecutive equal elements in a list with a new element

Question

In the code below I will replace all consecutive equal elements in a list with a new element. In this case I have chosen the new element to simply be the concatenation of all the equal elements, but I want the code to remain adaptable to other situations.

I have the following example:

Input: ["a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g"]
Output: ["aa", "b", "c", "ddd", "e", "ffff", "gg"]

I furthermore want to perform this replacement in a single-pass, meaning in \$\mathcal{O}(n)\$ time complexity and also with \$\mathcal{O}(1)\$ storage complexity.

In the code below I have implemented a solution to this problem, I believe it still satisfies \$\mathcal{O}(n)\$ but I'm not exactly sure because it also iterates back through the list to remove the elements.

private static void replaceConsecutiveEqualElements(final List<String> list) {
    ListIterator<String> listIterator = list.listIterator();
    String previousElement = null;
    int consecutiveMatches = 1;

    // Loop through list
    while (listIterator.hasNext()) {
        String element = listIterator.next();
        String newElement = null;

        if (element.equals(previousElement)) {
            consecutiveMatches++;
        }
        else {
            // Replace consecutive elements with new element
            if (consecutiveMatches >= 2) {
                listIterator.previous();
                for (int i = 0; i < consecutiveMatches; i++) {
                    listIterator.previous();
                    listIterator.remove();
                }
                newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
                listIterator.add(newElement);
            }
            consecutiveMatches = 1;
        }

        previousElement = (newElement == null) ? element : newElement;
    }

    // Special case for last element
    // Replace consecutive elements with new element
    if (consecutiveMatches >= 2) {
        for (int i = 0; i < consecutiveMatches; i++) {
            listIterator.previous();
            listIterator.remove();
        }
        String newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
        listIterator.add(newElement);
    }
}

Called like:

List<String> data = new ArrayList<>(Arrays.asList("a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g"));
replaceConsecutiveEqualElements(data);

I'm not happy at all with this code and am looking for feedback.

I have also decided to implement this in a functional programming language, in my case Clojure, though I have removed the time and storage complexity constraints.

(defn replace-consecutive-equal [seq]
  (->> seq
       (partition-by identity)
       (map (partial apply str))))

(println (replace-consecutive-equal '("a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g")))

The Clojure code roughly performs the following steps:

1. Take the input: ["a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g"]
2. Partition it by the identify function: [["a", "a"], ["b"], ["c"], ["d", "d", "d"], ["e"], ["f", "f", "f", "f"], ["g", "g"]]
3. Apply the str function on the elements of the inner lists via a map on the outer list, the str function effectively joins strings: ["aa", "b", "c", "ddd", "e", "ffff", "gg"]

As you can see this would have made the implementation a whole lot easier, unfortunately this is not possible due to the listed constraints.

Note: I am aware that this may be a case of premature optimization, but I feel that it is important to know how to implement such an algorithm efficiently.

Answer 1

You can remove the elements directly while iterating to avoid the back-iterating which would remove most of the method body. The add-call can be combined with one of the remove-calls to allow using set instead.

To reduce the amount of data to copy in case that your list is an ArrayList, the iterator should iterate the list backwards (assuming that you don't want to have a separated version for random-access lists):

private static void replaceConsecutiveEqualElements(
        final List<String> list) {
    ////
    for (final ListIterator<String> it = list.listIterator(list.size()); it.hasPrevious();) {
        final String sentinel = it.previous();
        int c = 0;
        for (; it.hasPrevious(); c++, it.remove()) {
            if (!it.previous().equals(sentinel)) {
                it.next();
                break;
            }
        }
        if (c != 0) {
            it.next();
            it.set(String.join("", Collections.nCopies(c + 1, sentinel)));
            it.previous();
        }
    }
}

Answer 2

Even without changing the basic algorithm, there are some optimizations that can be made.

        if (element.equals(previousElement)) {
            consecutiveMatches++;
        }
        else {

If we remove as we go, we don't need to change the previousElement, as it stays the same. So we can

        if (element.equals(previousElement)) {
            consecutiveMatches++;
            it.remove();
            continue;
        }

Then we can get rid of the else clause and just do everything at the same level of indent.

        previousElement = (newElement == null) ? element : newElement;

You only need the check for the case where the iterator was moved to the previous element. You only need it then because the marker is on the wrong element. You could just set consecutiveMatches to 0 instead of 1 in the original. Or advance the pointer back to where it should be.

            if (consecutiveMatches >= 2) {
                listIterator.previous();
                for (int i = 0; i < consecutiveMatches; i++) {
                    listIterator.previous();
                    listIterator.remove();
                }
                newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
                listIterator.add(newElement);
            }

But there's a simpler solution.

        if (consecutiveMatches >= 2) {
            listIterator.previous();
            listIterator.previous();
            newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
            listIterator.set(newElement);
        }

Because we removed the excess instances as we went, we can skip that here. We just need to replace the first instance with the combined version. The set command does this and it puts the next pointer in the right place.

Then we can just say

        previousElement = element;

This also fixes a bug in the original. The original would reduce [a, a, aa] to [aaaa] but the description says that it should be [aa, aa]. Sure, this never happens with the given inputs, but you say you don't want to be limited to those inputs.

    if (consecutiveMatches >= 2) {
        for (int i = 0; i < consecutiveMatches; i++) {
            listIterator.previous();
            listIterator.remove();
        }
        String newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
        listIterator.add(newElement);
    }

We need to fix this as well, so it doesn't remove the wrong elements.

    if (consecutiveMatches >= 2) {
        listIterator.previous();
        String newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
        listIterator.set(newElement);
    }

Making it generic

public interface Duplicator<T, U> {

    public U duplicate(int count, T element);

}

Implemented as

public class AppendStringDuplicator implements Duplicator<String, String> {

    @Override
    public String duplicate(int count, String element) {
        return String.join("", Collections.nCopies(count, element));
    }

}

Then you can change

private static void replaceConsecutiveEqualElements(final List<String> list) {

to

private static void replaceConsecutiveEqualElements(final List<String> list, Duplicator<String, String> duplicator) {

and

                String newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));

to

                String newElement = duplicator.duplicate(consecutivesCount, previousElement);

Now if you want to change to a different aggregation method, you can. You just define a new implementation of Duplicator and use it in

replaceConsecutiveEqualElements(data, new AppendStringDuplicator());

Complexity analysis

I concur, linear time. Even though your original goes forward and back, it never goes over anything more than twice.

This could increase storage use though. Note that duplicate strings like "a" and "a" may use the same storage for both. But "aa" is a new string. It uses new storage.