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

Оптимальное решение — два прохода по строке. Сначала подсчитываем количество вхождений каждого символа в массив фиксированного размера (например, int[26] для строчных латинских букв). Затем проходим строку второй раз и возвращаем первый символ, у которого счётчик равен единице. Временная сложность — O(n), пространственная — O(1) (26 целых чисел).

Если строка может содержать заглавные латинские буквы — расширяем массив до 52. Для любого ограниченного алфавита такой массив эффективнее хеш-таблицы — нет накладных расходов на хеширование и разрешение коллизий.

Пример реализации на Java:

public char firstUniqueChar(String s) {
    if (s == null || s.isEmpty()) {
        return '\0'; // или выбросить исключение
    }
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= 'a' && c <= 'z') {
            freq[c - 'a']++;
        }
        // если нужна поддержка заглавных — добавить else if
    }
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= 'a' && c <= 'z' && freq[c - 'a'] == 1) {
            return c;
        }
    }
    return '\0'; // нет уникальных
}

Граничные случаи обрабатываем явно: пустая строка — возвращаем нулевой символ (или индикатор отсутствия). Если все символы встречаются более одного раза — то же самое.

Альтернатива — LinkedHashMap для подсчёта за один проход (при обновлении счётчика потом пройти по карте). Но это даёт O(n) по времени и O(k) по памяти, где k — количество уникальных символов (до 26). Профита в простоте нет, а памяти — больше. Массив проще и быстрее на практике.