Удалить повторения символов из списка, начиная с 3-го повторения

62. Удалить повторения символов, начиная с третьего

Условие задачи:
Дан список символов List<Character>. Необходимо оставить первые два появления каждого символа, а третье и все последующие удалить.

Код:

public void removeDuplicatesFromThird(
        List<Character> chars
) {
    // код тут
}

Примеры:

[a, b, a, a, c, b, b] → [a, b, a, c, b]

[x, x, x, x] → [x, x]

[m, n, o] → [m, n, o]

Спойлеры к решению

Подсказки

💡 Храни количество появлений каждого символа в Map.
💡 Для безопасного удаления во время обхода используй Iterator.
💡 Удаляй элемент, если его новое количество появлений больше двух.

Решение

public void removeDuplicatesFromThird(
        List<Character> chars
) {
    if (chars == null) {
        throw new IllegalArgumentException(
                "List must not be null"
        );
    }

    Map<Character, Integer> counts = new HashMap<>();
    Iterator<Character> iterator = chars.iterator();

    while (iterator.hasNext()) {
        Character character = iterator.next();

        int count = counts.merge(
                character,
                1,
                Integer::sum
        );

        if (count > 2) {
            iterator.remove();
        }
    }
}

Iterator.remove() безопасно удаляет текущий элемент во время обхода списка и не приводит к ConcurrentModificationException.

Порядок оставшихся символов сохраняется.

Временная сложность — O(n), дополнительная память — O(k), где k — количество уникальных символов.