Как найти уникальный символ в строке

Давайте решим простую задачку, связанную с обработкой строк в Python.

# Определите, все ли символы в строке уникальны. 
# Использовать дополнительные структуры данных нельзя.

Довольно просто, верно? Это, собственно,
первое задание из раздела «Массивы и
строки» в книге «Cracking the Coding Interview». При
решении этой задачи мы можем применить
разные подходы, причем пространственная
и временная сложность в них будет
отличаться. Давайте рассмотрим парочку
вариантов.

Первый подход: брутфорс

Брутфорс (англ. brute force — грубая сила) —
это обычно самый простой способ решения
любой задачи на белой доске, так что
будет полезным начать именно с него.
Имея брутфорс-решение, мы сможем
воспользоваться хотя бы им, если более
элегантные методы не сработают. Также
это хорошая практика в основах
программирования. Читая это решение,
вы лучше поймете, с какого конца вообще
надо браться за задачи.

Название «брутфорс» говорит само за
себя. Представьте, что у вас есть набор
пазлов, где все кусочки одного цвета.
Вам придется вслепую пробовать каждую
комбинацию, пока не найдете пару пазлов,
которые можно соединить. Что касается
нашей задачи, мы будем сверять каждый
символ в строке со всеми остальными,
пытаясь найти совпадения.

Начнем с определения метода (можете работать в Repl.it, а можете воспользоваться просто карандашом и бумагой). Наш метод будет принимать одну строку в качестве параметра. Ее мы обозначим как s.

def is_unique(s):
    pass

Дальше мы определим наш первый цикл for. Вообще у нас будут вложенные циклы, а этот будет перебирать все символы в строке до предпоследнего (включительно). Почему не до последнего? Потому что каждый из этих символов мы будем сравнивать с теми, которые идут после него, а за последним больше нет других символов.

def is_unique(s):
    for i in range(len(s) - 1):

Теперь давайте сделаем второй цикл for внутри первого. Он будет начинаться от следующей позиции в списке, которой мы назначим индекс j. Индекс j будет расти до конца списка, а элементы под этим индексом будут сравниваться с символом под индексом i. В случае совпадения мы вернем False — это будет означать, что не все символы в строке уникальны.

def is_unique(s):
    for i in range(len(s) - 1):
        for j in range(i + 1, len(s)):
            if s[j] == s[i]:
                return False

Наконец, нам нужно где-нибудь вернуть
True. Если вложенный цикл for успешно сравнил
все символы и не нашел совпадений,
значит, все символы в строке уникальны.
Поэтому мы возвращаем True за пределами
вложенного цикла.

def is_unique(s):
    for i in range(len(s) - 1):
        for j in range(i + 1, len(s)):
            if s[j] == s[i]:
                return False
    return True

Вот и все! Вызов is_unique("Hello") должен вернуть False, а is_unique("Bye") — True.

Временная и пространственная
сложность брутфорс-метода

Прежде всего, наше решение удовлетворяет
требованию «никаких дополнительных
структур данных». Мы просто перебираем
в цикле строку, не сохраняя информацию
в новой структуре. Это дает нам
пространственную сложность O(1), которая
не зависит от длины строки.

Как насчет временной сложности?
Представим наихудший случай. В строке
нет уникальных символов, поэтому
вложенный цикл отрабатывает все до
конца. Временная сложность здесь будет
примерно O(N2), несмотря на то, что мы
экономим некоторое время, проверяя
каждую пару только единожды. O(N2) это
ужасно. Но это, вероятно, наилучший
вариант, если нельзя создавать
дополнительные структуры данных или
модифицировать исходную строку.

Более оптимальный подход:
сортировка строки

Теперь, когда мы рассмотрели брутфорс, давайте перейдем к более элегантным решениям. Давайте посмотрим, нельзя ли применить здесь концепцию поиска и сортировки. Если мы отсортируем строку, мы сможем перебирать ее в цикле, проверяя, не совпадает ли каждый из символов с предыдущим.

Метод Python .sort() работает только со списками. Так что наша первая задача — превратить строку в список символов. Мы показываем, как это делается, что если вы дойдете до собеседования с решением задач у доски, такие вещи у вас должны уже от зубов отскакивать.

s_as_list = [char for char in s]

Цикл for перебирает все символы в строке s и возвращает каждый символ. Мы записываем результат в список, взяв цикл в квадратные скобки.

Превратив строку в список, мы можем вызвать метод sort().

def is_unique2(s):
    s_as_list = [char for char in s]
    s_as_list.sort()

Теперь мы можем перебрать список. Мы
будем сравнивать каждую букву с
предыдущей.
Сделать это можно двумя способами. Можно
проитерировать каждый индекс, с первого
(если таковой существует) до последнего.
А если не отслеживать индекс, можно
сохранять предыдущую букву в переменную.
Инициализировать переменную можно как
пустую строку.

    prev = ""
    for letter in s_as_list:

На каждой итерации нам нужно сделать
одно из двух:

1. Если символ такой же, как и предыдущий,
   вернуть False.
2. В противном случае сделать этот
   символ новым предыдущим символом.

Можно превратить это в предложение if. Давайте используем в качестве имени переменной letter, а не char, чтобы не путать с тем, что мы делали ранее, когда превращали строку в список.

    prev = ""
    for letter in s_as_list:
        if letter == prev:
            return False
        else: 
            prev = letter

Наконец, если цикл for успешно отработает и не найдет совпадений, мы вернем True за пределами цикла. Все вместе это выглядит так:

def is_unique2(s):
    s_as_list = [char for char in s]
    s_as_list.sort()
    prev = ""
    for letter in s_as_list:
        if letter == prev:
            return False
        else: 
            prev = letter
    return True

Временная сложность решения
с использованием метода sort()

Временная сложность этого решения зависит от временной сложности самого метода sort(). Python использует Timsort — гибрид сортировки слиянием и вставками (если вам это о чем-то говорит). Его временная сложность в среднем и наихудшем случае — O(N log N). Кроме того, мы перебираем список в цикле N раз, но этим можно пренебречь, потому что O(N log N) больше.

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

Решение, еще более оптимальное
с точки зрения временной сложности:
использование словаря

Давайте вообще отбросим запрет на
дополнительные структуры данных. Какое
решение еще можно предложить в таком
случае? В книге Cracking the Coding Interview первое
решение предполагает использование
массива с длиной 128 (длина всего алфавита
Unicode). Но если вы уже пользовались Python
пару раз, вы, вероятно, знакомы с такой
структурой как словарь.

В Python есть библиотека с дефолтным словарем — defaultdict. Она позволяет нам задавать значения по умолчанию: при вызове ключа, которого нет в словаре, будет создана пара из этого ключа и дефолтного значения. Это избавляет нас от необходимости проверять, есть ли ключ в списке, перед поиском его значения.

Мы можем назначить нашему словарю dd тип bool, таким образом дефолтное значение всегда будет False.

from collections import defaultdict

def is_unique3(s):
    dd = defaultdict(bool)

Теперь давайте напишем цикл for. Мы переберем в цикле все символы в строке, проверяя их значение. Если значение будет True, это будет означать, что такой символ нам уже попадался. В таком случае мы вернем False. Если значение будет False (а defaultdict «выдаст» его любому ключу, которого еще нет в словаре), мы присвоим этому символу значение True.

    for char in s:
        if dd[char]:
            return False
        dd[char] = True

Наконец, мы вернем True за пределами
цикла, если каждый символ встретится
только один раз.

Все вместе это выглядит следующим
образом:

def is_unique3(s):

    dd = defaultdict(bool)

    for char in s:
        if dd[char]:
            return False
        dd[char] = True
    return True

Временная сложность решения
со словарем

Мы перебираем список N раз, кроме того
доступ к каждому элементу словаря имеет
временную сложность O(1). Таким образом
временная сложность этого решения —
O(N), а это даже лучше, чем в предыдущем
способе. Работая над программами, вы
увидите, что компромиссы с пространственной
и временной сложностью — ваши постоянные
спутники, а то, какое решение считать
наилучшим, зависит от ситуации.