First Unique Character in a String

+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 — трижды, а e — один раз, с индексом 8. Но y тоже встречается один раз, с индексом 4, и она появляется первой, поэтому ответ — 4.

Ввод: s = "swiss"
Вывод: 1
Пояснение: В swiss буква s встречается три раза. Буква w с индексом 1 встречается один раз, и то же верно для i с индексом 2; побеждает первая из них, поэтому ответ — 1.

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

+17 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

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

Проверка должна охватывать всю строку — и до i, и после неё. Более ранняя копия в строке лишает букву уникальности так же, как и более поздняя.

В большинстве строк остановка при обнаружении первой копии помогает, но не во всех. Если каждая буква встречается в длинной последовательности, например сначала 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 счётчиков хранит все количества: индекс 0 соответствует a, а индекс 25 — z. Индекс буквы — это её код символа минус код a.

Первый проход заполняет счётчики. Для coddycode они показывают: c: 2, o: 2, d: 3, y: 1, e: 1. Второй проход идёт по строке слева направо и останавливается на первой позиции, буква которой встречается 1 раз. Это y с индексом 4. Второй проход должен идти по строке, а не по 26 счётчикам, потому что вопрос касается первой позиции, а не первой буквы алфавита.

Оба прохода читают строку по одному разу, поэтому время работы — 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, то есть b.
Возвращается буква вместо её индекса или индекс нумеруется с 1. В Lua и R отсчёт начинается с 1, поэтому перед возвратом нужно вычесть 1.
Забывается случай -1. В такой строке, как aabbcc, нет уникальной буквы, и функция всё равно должна возвращать значение после цикла.
Счётчики индексируются по необработанному коду символа. a — это 97, что далеко за пределами массива из 26 элементов; сначала нужно вычесть код a.

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

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

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

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

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

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

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

Почему второй проход проходит по строке, а не по счётчикам?

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "coddycode"

Ожидается