387. First Unique Character in a String

LeetCode задача 387

Задача

Дана строка s. Найдите первый уникальный символ в строке и верните его индекс. Если такого символа нет, верните -1.

Подсказки

Использование хеш-таблицы может ускорить процесс поиска уникальных символов.

Подход

1. Инициализация: Создайте хеш-таблицу для хранения частоты каждого символа в строке.
2. Первый проход: Пройдите по строке и заполните хеш-таблицу.
3. Второй проход: Пройдите по строке второй раз и проверьте частоту каждого символа в хеш-таблице. Первый символ с частотой 1 будет ответом.

Этот подход прост для понимания и реализации. Он требует двух проходов по строке, но временная сложность остается линейной.

Алгоритм

1. Создайте хеш-таблицу для хранения частот символов.
2. Пройдите по строке, заполняя хеш-таблицу.
3. Пройдите по строке второй раз, и для каждого символа проверьте его частоту в хеш-таблице. Верните индекс первого символа с частотой 1.

Решение

def firstUniqChar(s: str) -> int:
    # Хеш-таблица для хранения частот символов
    char_count = {}
    
    # Первый проход: заполнение хеш-таблицы
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1

    # Второй проход: проверка частоты символов
    for index, char in enumerate(s):
        if char_count[char] == 1:
            return index
            
    return -1