Я пытаюсь решить проблему с лит-кодом № 3, но лимит времени превышен

Я пытаюсь решить проблему LeetCode 3. Самая длинная подстрока без повторяющихся символов:

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

Пример 1:

Ввод: s = "abcabcbb"
Выход: 3
Пояснение: Ответ: «abc» длиной 3.

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

#returns true if there is a duplicate character
def count_characters(self,s):
    for i in s:
        if s.count(i)>1:
            return True
    return False

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    #generate list of all substrings
    max_len = 0 

    for i in range(len(s)):
        for j in range(i+1, len(s)+1):
            substr = s[i:j]
            if len(substr)>max_len and not self.count_characters(substr):
                    max_len = len(substr)
            print(substr)

    return max_len

Что мне следует сделать, чтобы пройти тесты с более длинными входными данными, чтобы не истечь тайм-аутом?

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

Barmar 05.06.2024 22:57

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

Barmar 05.06.2024 23:06

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

Barmar 05.06.2024 23:07

вы можете проверить наличие дубликатов, выполнив len(set(substr)) == len(substr), большая часть кода выполняется на C, поэтому он будет быстрее, чем любой необработанный цикл, который вы когда-либо могли написать.

Ahmed AEK 05.06.2024 23:26

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

Ahmed AEK 05.06.2024 23:31
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
5
94
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

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

Таким образом, во внутреннем цикле достаточно зациклить до 26 букв общей сложностью O(N * 26).

Ответ принят как подходящий

Ваш подход не эффективен. Благодаря двум вложенным циклам выражение s[i:j] вычисляется O(𝑛²) раз, а само это выражение имеет временную сложность O(𝑚), где 𝑚 — размер среза. Это приводит к общей сложности O(𝑛³).

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

Эту проблему можно решить с временной сложностью O(𝑛).

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

Вот еще несколько советов, если они вам понадобятся:

раздвижное окно

индекс появления последнего символа, на каждый символ

И напоследок реализация спойлера:

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last_occurence = {} # per character: last found index for it exclude = -1 # index before the current substring's start longest = 0 for i, ch in enumerate(s): exclude = max(exclude, last_occurence.get(ch, -1)) last_occurence[ch] = i longest = max(longest, i - exclude) return longest

спойлер очень крутой.

user24714692 06.06.2024 02:15

да, в пятницу я не знал, что это сработало

rynl1 06.06.2024 14:39

Вы можете следовать стандартному процессу решения раздвижного окна:

  1. Используйте левый и правый указатель (индексы), чтобы представить текущий лучший ответ, заканчивающийся правым индексом.
  2. Продолжайте перемещать правый указатель вверх, пока текущее окно является действительным, каждый раз обновляя ответ ответом для текущего окна. Остановитесь, когда правый указатель достигнет конца.
  3. Когда текущее окно станет недействительным, продолжайте перемещать левый указатель вверх, пока текущее окно снова не станет действительным. Вернитесь к шагу 2.

Это непосредственно приводит к линейному (O(N)) решению следующим образом.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        curr = set()
        l = ans = 0
        for r, c in enumerate(s):
            while c in curr:
                curr.remove(s[l])
                l += 1
            curr.add(c)
            ans = max(ans, r - l + 1)
        return ans

Другие вопросы по теме