Удалить повторения элементов, начиная с третьего вхождения

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

Условие задачи:

Написать метод, который принимает список символов и удаляет все повторения каждого символа, начиная с третьего вхождения.

Порядок элементов в исходном списке должен быть сохранён.

Каждый символ может встретиться в результирующем списке не более двух раз.

Пример:

Input:
[A, B, A, B, A, B, C, C, D, C, C]

Output:
[A, B, A, B, C, C, D]

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

Подсказки

💡 Необходимо отслеживать, сколько раз каждый символ уже встретился при обходе списка.

💡 Для хранения количества вхождений удобно использовать Map<Character, Integer>.

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

Решение

Для каждого символа будем хранить количество его предыдущих вхождений.

Во время обхода исходного списка:

Получаем текущее количество вхождений символа.
Если символ встретился менее двух раз, добавляем его в результирующий список.
Увеличиваем счётчик вхождений символа.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {

    public static List<Character> removeDuplicates(List<Character> chars) {
        Map<Character, Integer> occurrences = new HashMap<>();
        List<Character> result = new ArrayList<>();

        for (Character ch : chars) {
            int count = occurrences.getOrDefault(ch, 0);

            if (count < 2) {
                result.add(ch);
            }

            occurrences.put(ch, count + 1);
        }

        return result;
    }

    public static void main(String[] args) {
        List<Character> input = List.of(
                'A', 'B', 'A', 'B', 'A', 'B',
                'C', 'C', 'D', 'C', 'C'
        );

        System.out.println(removeDuplicates(input));
    }
}

Результат:

[A, B, A, B, C, C, D]

Map позволяет хранить количество появлений каждого символа. При этом мы обходим список только один раз, поэтому порядок элементов сохраняется.

Если символ встретился в первый или второй раз, он добавляется в результат. Начиная с третьего вхождения символ пропускается.

Сложность:

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