[Вопрос интервью] Самая длинная подстрока без повторяющихся персонажей

Автор оригинала: Shubham Sayon.

🏗️ Теги компании: Как сообщает многочисленные программисты по всему миру, этот вопрос был задан в кодировании интервью/раундов компаний, как:

Амазонка
Амантичный
Bloomberg
ЙЛП

Итак, если вы готовитесь к вашему предстоящему кодирующему интервью, то вам вполне могут столкнуться на этот вопрос в вашем кодировании. Можете ли вы решить это оптимально?

Постановка проблемы

Учитывая строку « S ». Найти Самая длинная подстрока не повторяя никаких персонажей.

⚠️ Ограничения:

0,90 ⁴
S состоит из английских букв, цифр, символов и пробелов.

Примечание: В формальной теории языка и информатики, Подстрока это непрерывная последовательность символов в строке.

(Источник: Википедия )

💡examples.

Давайте посмотрим на некоторые примеры для улучшения нашего понимания этой проблемы.

Example 1

Input s = "xyzxyzyy"
Output: 3
Explanation: The longest substring is "xyz", with a length of 3.

Example 2

Input: s = "kkkkk"
Output: 1
Explanation: The longest substring is "k", with a length of 1.

Example 3

Input: s = "2455lmno#%kk"
Output: 8
Explanation: The longest substring is "5lmno#%k", with a length of 8.
Notice that the answer must be a substring, "245lmno#%k" is a subsequence and not a substring.

Example 4

Input: s = ""
Output: 0
Explanation: This is an edge case with a null string.

Example 5

Input: s = "tweet"
Output: 3
Explanation: The longest substring is "twe", with a length of 3.

🧐 Тидбит : ❖ A подпоследовательность строки – это новая строка, которая формируется из исходной строки, удаляя некоторые (может быть ни одного) символов, не нарушая относительные позиции оставшихся символов. Тогда как . Подстрока это « непрерывная последовательность » символов в строке. ❖ Подстрока также является подпоследовательностью, но не вице-версией. Пример: «Туз» является подпоследовательностью "ABCDE" Но это не подстрока. «ABC» это подстрока, а также подпоследовательность "ABCDE" Отказ

🖊️naïve подход: используя алгоритм грубой силы

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

❖ Подход: Основная идея этого алгоритма состоит в том, чтобы сканировать все подстроки один за другим и проверьте, содержит ли он какой-либо дубликат. Вам нужны все уникальные символы в результирующей подстроке. Таким образом, вам нужно хранить самую длинную подстроку без каких-либо повторяющихся символов в переменной, а затем вернуть его.

Мы можем повторить все возможные подстроки с помощью вложенного цикла.
Если в текущей подстроке нет дубликата, мы обновляем ответ длиной максимальной подстроки.
Однако, если встречается дубликат символ, мы вырываются из внутренней петли, а следующая подстрока учитывается.

Следующая диаграмма иллюстрирует подход, который следует здесь:

❖ Давайте посмотрим на код:

def largest_substring(s):
    lsub = 0
    for i in range(len(s)):
        curr = ""
        for j in range(i, len(s)):
            if s[j] not in curr:
                curr += s[j]
                lsub = max(lsub, len(curr))
            else:
                break
    return lsub

Давайте выполним этот код на наших примерах:

# Example 1
s = "xyzxyzyy"
print(largest_substring(s))
#3

# Example 2
s = "kkkkk"
print(largest_substring(s))
#1

# Example 3
s = "2455lmno#%kk"
print(largest_substring(s))
#8

# Example 4
s = ""
print(largest_substring(s))
#0

# Example 5
s = "tweet"
print(largest_substring(s))
#3

Ура! 😃 Прошло все тестовые случаи.

❖ Анализ: Рассмотрим строку « S » с размером « N ». В этом случае будет (N * (N + 1)/2) возможные подстроки. Следовательно, вложенное для петли имеет сложность O (n ^ 2) Отказ Таким образом, этот подход имеет временную сложность O (n ^ 2) Отказ

❖ Обсуждение: Хотя это в значительной степени работает, но это не эффективное решение. В этом подходе мы неоднократно проверяем каждую подстроку для уникальных символов. Но нам нужно проверить каждую подстроку?

🖊️solution 2: раздвижное окно

❖ Подход:

Мы можем оптимизировать метод грубой силы, используя Раздвижное окно техника. В этом решении мы будем продолжать пересекать строку слева направо, пока не сталкиваемся о любом повторении. Чтобы узнать длину текущего окна, мы будем использовать пару указателей/индексов. Мы также будем хранить карту для хранения подсчета уникальных персонажей и продолжайте обновлять, как мы продолжаем расширение или сокращение скользящего окна.

❖ Давайте посмотрим на алгоритм:

Инициализировать два указателя Я и J На 0. Эти указатели позволят нам определить размер скользящего окна.
Определите набор для хранения уникальных символов (набор не позволяет никаких дублирующих значений) и переменной « lon » для хранения длины самой длинной подстроки.
Начните сканирование строки:
- Если текущий символ произошел раньше (не присутствует в SET), добавьте символ на набор и увеличивайте J Указатель, а также обновить переменную « Lon », который хранит ответ.
- Иначе, если текущий символ был повторен (присутствует в наборе) по указателю до Я Установите « Lon » в качестве текущей длины скользящего окна и удалите символ при индексе Я , то есть, s [я] Отказ
Вернуть переменную ” lon “.

Вот пример, чтобы проиллюстрировать вышеуказанный алгоритм:

Объяснение:

Первоначально текущий индекс и точка окончательного индекса при первом индексе. Следовательно, мы начинаем с первого показателя строки и храните его в Установить Чар Отказ
Затем мы сдвигаем указатель J Направо. Таким образом, текущее окно расширяется, а длина подстроки одновременно увеличивается и сохраняется в переменной, которая удерживает дорожку длины самой длинной подстроки. Процесс повторяется до A повторяющийся характер найден. В этом случае повторяющийся символ найден в 3 ^Rd Итерация.
Как только повторяющийся персонаж найден, персонаж на Я ^TH Индекс удаляется из набора. В этом случае [T] удаляется в конце 3 ^Rd Итерация. Таким образом, набор сейчас содержит [W, E] После 3 ^Rd Итерация. Этот процесс повторяется, и после того, как вся строка пройдена, у вас будет длина самая большая подстрока, хранящаяся в выходной переменной.

❖ Теперь давайте посмотрим на код:

def largest_substring(s):
    i = j = lon = 0
    chars = set()
    while j < len(s):
        if s[j] not in chars:
            chars.add(s[j])
            j = j + 1
            lon = max(lon, len(chars))
        else:
            chars.remove(s[i])
            i = i + 1
    return lon

❖ Тестовые случаи: Давайте выполним примеры в этом коде, чтобы проверить, работает ли он.

# Example 1
s = "xyzxyzyy"
print(largest_substring(s))
#3

# Example 2
s = "kkkkk"
print(largest_substring(s))
#1

# Example 3
s = "2455lmno#%kk"
print(largest_substring(s))
#8

# Example 4
s = ""
print(largest_substring(s))
#0

# Example 5
s = "tweet"
print(largest_substring(s))
#3

Идеальный! Это прошло все тестовые случаи.

❖ Анализ сложности времени:

В этом решении мы должны пересечь строку только один раз, и, следовательно, Сложность времени будет линейным → O (n) Отказ

Чтобы убедиться, что ни один символ не повторяется внутри окна, мы использовали установленную структуру данных. Время поиска для этого – O (1) Отказ
В худшем случае каждый символ в строке будет посещен дважды, учитывая сложность O (2 * n) Отказ
Таким образом, общая сложность выполнения = O (1) + O (2 * N) ~ O (n) Отказ

🖊️Optimal Решение: используя словарь

❖ Подход:

Мы можем немного оптимизировать вышеуказанный код, используя Словарь Отказ Предыдущее решение требует максимума 2n шаги. Но это может быть дополнительно оптимизировано, чтобы требовать только N шаги. Используя этот подход, вы можете сразу пропустить больше символов, когда найден повторяющийся символ. Вы можете сделать это, составляя каждый символ к его индексу. Причина: Если S [J] является дубликатом символа в диапазоне [I, j) с индексом j ‘, вам не нужно увеличивать я один за раз. Вместо этого вы можете просто пропустить все элементы в диапазоне [I, J ‘] и установите i, чтобы быть J ‘+ 1 напрямую.

Вот иллюстрация концепции:

Объяснение :

Индекс каждого символа хранится в виде пар клавиш в словаре hmap Отказ Переменная Лон который используется для хранения длины самой длинной подстроки, также обновляется такое, что Лон хранит результат Макс (Лон, J-I + 1) Отказ
- Примечание: Изначально,
Как только персонаж повторяется, элементы в пределах диапазона [я, j ‘] пропущены и Я установлен на J ‘+ 1 Отказ В этом случае повторяющийся символ найден в 4 ^TH Итерация. Таким образом, все символы в диапазоне [0,2] пропущены и Я Установлено на точку на 3 ^Rd показатель.
- Примечание: J ' представляет собой индекс повторяющегося символа. В этом примере J ‘(4 итерация) Для повторяющегося символа Е и J ‘= 1 (5 итерация) Для повторения характера Т.
После полного выполнения петли длина наибольшего элемента будет храниться в пределах переменной “Лон”.

❖ Теперь давайте посмотрим на код:

def largest_substring(s):
    i = lon = 0
    hmap = {}
    for j in range(0, len(s)):
        if s[j] in hmap:
            i = max(i, hmap[s[j]] + 1)
        hmap[s[j]] = j
        lon = max(lon, j-i+1)
    return lon

❖ Анализ сложности: Используя этот подход, вы должны отсканировать строку слева на звонок только один раз Отказ Это означает, что цикл пройдет N итерации. Таким образом, момент сложности для этого решения будет O (n) Отказ

ВХОД	ВЫХОД	На)
xyzxyzyy.	3	O (3)
Ккккк	1	O (1)
2455LMNO #% Kk	8	O (8)
	0	O (1)
твитнуть	5	O (5)

Вывод

Я надеюсь, что вам понравилось этот опрос кодирования. Пожалуйста, оставайся настроенными и Подписаться Для более интересных проблем кодирования.

Рекомендуется: Академия компьютерной науки Finxter

Вы хотите быстро освоить самые популярные Python IDE?
Этот курс приведет вас от новичка к эксперту в Пычарме в ~ 90 минут.
Для любого разработчика программного обеспечения имеет решающее значение для освоения IDE хорошо, писать, тестировать и отлаживать высококачественный код с небольшим усилием.

Присоединяйтесь к Pycharm MasterClass Сейчас и мастер Pycharm на завтра!

✍️ Почтовые кредиты: Шубхам Сайон и Раши Агарваль

Я профессиональный Python Blogger и Content Creator. Я опубликовал многочисленные статьи и создал курсы в течение определенного периода времени. В настоящее время я работаю полный рабочий день, и у меня есть опыт в областях, таких как Python, AWS, DevOps и Networking.

Вы можете связаться со мной @: