День 7 – Дольше всего подстрока без повторяющихся персонажей

Проблема

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

Пример 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Пример 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Пример 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Пример 4:

Input: s = ""
Output: 0

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

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

Мои тесты

Ссылка на код

import pytest
from .Day7 import Solution

s = Solution()


@pytest.mark.parametrize(
    "input,expected",
    [
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("ababc", 3),
        ("dvdf", 3),
        ("", 0),
    ],
)
def test_length_of_longest_substring(input, expected):
    assert s.lengthOfLongestSubstring(input) == expected

Мое решение

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        size = len(s)
        if size < 2:
            return size

        current_longest = 0
        sub = ""

        for c in s:
            if c not in sub:
                sub += c
                if len(sub) > current_longest:
                    current_longest = len(sub)
            else:
                sub = f"{sub.split(c)[1]}{c}"

        return current_longest

Анализ

Мой комментарий

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

Первый шаг должен был проверить, является ли строка одним символом или пустой. Ответ 1 или 0 соответственно в этом случае.

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

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

Пока у нас нет повторяющегося персонажа, мы увеличиваем Current_longest Номер, если текущая строка длиннее этого.

Если мы столкнулись с повторяющимся символом, нам нужно начать новую подстроку. Нам нужно начать эту новую строку на персонаже после последнего повторяющегося символа. Так что, если у нас была строка DV И следующий персонаж, который мы сталкиваемся, это D Нам нужно создать новую подстроку vd Удаление первого d .

В конце концов, мы возвращаем Current_longest номер.

Оригинал: “https://dev.to/ruarfff/day-7-longest-substring-without-repeating-characters-12mb”