First Unique Character in a String

Q: Какова временная сложность задачи «Первый уникальный символ в строке»?

Подсчёт букв, а затем просмотр строки — это два прохода по n шагов, поэтому время выполнения составляет O(n) . Для 26 счётчиков требуется одинаковый объём памяти независимо от длины строки, поэтому дополнительная память составляет O(1) .

ЛегкоХеширование

+10

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

Функция

firstUniqChar(s: string) → integer

sstring: строка для поиска, только строчные буквы
Возвращаетinteger: индекс первой буквы, которая встречается ровно один раз, или -1, если такой нет

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит только строчные английские буквы (a–z).

Примеры

Ввод: s = "coddycode"
Вывод: 4
Пояснение: В coddycode буквы c и o встречаются дважды, а d — трижды. И y (индекс 4), и e (индекс 8) встречаются один раз, и y стоит первой, поэтому ответ — 4.

Ввод: s = "swiss"
Вывод: 1
Пояснение: Буква s встречается три раза. И w с индексом 1, и i с индексом 2 встречаются по одному разу, причем w идет раньше.

Ввод: s = "aabbcc"
Вывод: -1
Пояснение: Каждая буква в aabbcc встречается дважды, поэтому ответ — -1.

Дополнительный вопрос

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

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Буква, которая кажется уникальной, когда ты до неё доходишь, может повториться в самом конце строки, поэтому одного просмотра слева направо недостаточно. Сначала посчитай каждую букву, а затем второй проход позволит за постоянное время определить, содержит ли каждая позиция уникальную букву.

Найдите вторую копию каждой буквы

Верно, но не успевает на самых больших тестах

Идея

Для каждой позиции, начиная слева, просканируй всю строку в поисках другой позиции с той же буквой. Проверяй обе стороны: более раннее вхождение исключает букву не меньше, чем более позднее. Ответ — первая позиция, для которой нет совпадений. В coddycode для позиций с 0 по 3 находится совпадение, а для y с индексом 4 — нет.

Остановка при первом совпадении не помогает, если каждая буква расположена в одном длинном блоке, например 2000 букв a, затем 2000 букв b и так далее: при каждом сканировании приходится проходить все предыдущие блоки. При n = 5 × 10^4 это более миллиарда сравнений.

Алгоритм

Для каждого индекса i слева направо:
Просматривай все индексы j, кроме i, и остановись на первом, для которого s[j] равно s[i].
Если такого j нет, верни i.
Если для каждого индекса нашлась копия, верни -1.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

Подсчитайте буквы, затем выполните сканирование

Идея

Подсчитывайте каждую букву один раз вместо того, чтобы заново искать её для каждой позиции. Существует всего 26 букв, поэтому 26 счётчиков хранят все количества; индекс счётчика определяется кодом буквы за вычетом кода a.

Первый проход заполняет счётчики; для coddycode только значения счётчиков для y и e в итоге равны 1. Второй проход перебирает строку слева и останавливается на первой букве, счётчик которой равен 1, — это y с индексом 4. Два прохода по n шагов дают временную сложность O(n), а 26 счётчиков требуют O(1) памяти при любой длине строки.

Алгоритм

Создай массив из 26 нулей.
Для каждой буквы в s увеличивай её счётчик на 1.
Ещё раз пройди по s, начиная с индекса 0. Верни первый индекс, буква по которому имеет счётчик, равный 1.
Если обход закончится, верни -1.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

Ловушки и крайние случаи

Проверка только букв перед позицией i. В abca у первой a нет копии перед ней, но она не является уникальной.
Во втором проходе перебор массива счётчиков вместо строки. Для ba первый счётчик, равный 1, соответствует a, но ответ — индекс 0.
Использование кода символа напрямую для индексации счётчиков. a — это 97, что далеко за пределами массива из 26 счётчиков.
Возврат буквы вместо её индекса или индекса с нумерацией от 1 в Lua или R.

Частые вопросы3

Какова временная сложность задачи «Первый уникальный символ в строке»?

Подсчёт букв, а затем просмотр строки — это два прохода по n шагов, поэтому время выполнения составляет O(n). Для 26 счётчиков требуется одинаковый объём памяти независимо от длины строки, поэтому дополнительная память составляет O(1).

Сможешь решить эту задачу за один проход по строке?

Да. За один проход сохраните для каждой буквы индекс её первого появления или отметьте её как повторяющуюся, когда она встретится снова. Затем найдите наименьший индекс среди 26 букв, встретившихся один раз. Строка читается один раз, а заключительная проверка занимает 26 шагов.

Что использовать для подсчёта букв: хеш-таблицу или массив?

Если используются только строчные буквы, массив из 26 счётчиков будет меньше и быстрее. Хеш-таблица — правильный выбор, если строка может содержать любые символы, например текст в Unicode. Алгоритм остаётся тем же: подсчитать, а затем просканировать строку.

def firstUniqChar(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "coddycode"

Ожидаемый вывод