Поиск первого уникального символа

14. Найти первый уникальный символ в строке

Условие задачи:
Необходимо реализовать метод findFirstUniqueLetter(String str), который возвращает первый символ строки, встречающийся ровно один раз.

Если уникальных символов нет, можно вернуть специальное значение, например пробел ' '.

Код:

public class Main {

    public static void main(String[] args) {
        test();
    }

    private static char findFirstUniqueLetter(String str) {
        // Write your code here
    }

    private static void test() {
        Map<String, Character> testInOut = new HashMap<>() {{
            put("summer time sadness", 'u');
            put("AA bb CC d", 'd');
        }};

        testInOut.forEach((input, expected) -> {
            char answer = findFirstUniqueLetter(input);

            if (answer == expected) {
                System.out.println("Passed");
            } else {
                System.out.printf(
                        "Not passed. Received %s but expected %s%n",
                        answer,
                        expected
                );
            }
        });
    }
}

Примеры:

findFirstUniqueLetter("summer time sadness") → 'u'
findFirstUniqueLetter("AA bb CC d")           → 'd'

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

Подсказки

💡 Сначала посчитай количество вхождений каждого символа.
💡 Для подсчёта удобно использовать HashMap<Character, Integer>.
💡 Затем ещё раз пройди по исходной строке слева направо.
💡 Первый символ с частотой 1 и будет ответом.

Решение

private static char findFirstUniqueLetter(String str) {
    Map<Character, Integer> frequencies = new HashMap<>();

    for (char ch : str.toCharArray()) {
        frequencies.merge(ch, 1, Integer::sum);
    }

    for (char ch : str.toCharArray()) {
        if (frequencies.get(ch) == 1) {
            return ch;
        }
    }

    return ' ';
}

На первом проходе:

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

подсчитывается количество появлений каждого символа.

На втором проходе строка просматривается в исходном порядке:

for (char ch : str.toCharArray()) {
    if (frequencies.get(ch) == 1) {
        return ch;
    }
}

Поэтому возвращается именно первый уникальный символ.

Для строки:

summer time sadness

первым символом, встречающимся один раз, является:

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

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

Возврат ' ' используется как специальное значение согласно условию. В реальном коде, если пробел сам может быть уникальным символом, лучше изменить контракт метода и возвращать Optional<Character>.