Поиск наименее частого слова в строке

26. Найти слово с минимальной частотой встречаемости

Условие задачи:
Дана очень длинная строка text.

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

Если несколько слов имеют одинаковую минимальную частоту, можно вернуть любое из них.

Код:

public class RareWordFinder {

    public static String findLeastFrequentWord(String text) {
        // TODO
    }
}

Пример:

Вход:
"apple orange banana apple pear banana apple"

Частоты:
apple  → 3
banana → 2
orange → 1
pear   → 1

Результат:
"orange" или "pear"

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

Подсказки

💡 Для каждого слова нужно посчитать количество его появлений через HashMap<String, Integer>.
💡 После подсчёта пройди по Map и найди запись с минимальным значением.
💡 Поскольку строка может быть очень длинной, необязательно создавать массив всех слов через split().
💡 Если нужно игнорировать регистр и пунктуацию, слова удобно извлекать через регулярное выражение.

Решение

public static String findLeastFrequentWord(String text) {
    if (text == null || text.isBlank()) {
        return null;
    }

    Map<String, Integer> frequencies = new HashMap<>();

    Matcher matcher = Pattern
            .compile("[\\p{L}\\p{N}]+")
            .matcher(text);

    while (matcher.find()) {
        String word = matcher.group().toLowerCase(Locale.ROOT);
        frequencies.merge(word, 1, Integer::sum);
    }

    String rareWord = null;
    int minFrequency = Integer.MAX_VALUE;

    for (Map.Entry<String, Integer> entry : frequencies.entrySet()) {
        if (entry.getValue() < minFrequency) {
            minFrequency = entry.getValue();
            rareWord = entry.getKey();
        }
    }

    return rareWord;
}

Сначала слова извлекаются из строки:

Matcher matcher = Pattern
        .compile("[\\p{L}\\p{N}]+")
        .matcher(text);

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

Для каждого найденного слова увеличивается счётчик:

frequencies.merge(word, 1, Integer::sum);

Например:

apple  → 3
orange → 1
banana → 2
pear   → 1

После этого достаточно найти минимальное значение в карте:

for (Map.Entry<String, Integer> entry : frequencies.entrySet()) {
    if (entry.getValue() < minFrequency) {
        minFrequency = entry.getValue();
        rareWord = entry.getKey();
    }
}

Если несколько слов имеют одинаковую минимальную частоту, будет возвращено одно из них, что соответствует условию задачи.

Для примера:

String text =
        "apple orange banana! apple, pear? banana apple";

System.out.println(findLeastFrequentWord(text));

результатом может быть:

orange

или:

pear

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