MEDIUM 0003. Longest Substring Without Repeating Characters

Problem Statement

Leetcode Link

Examples

Solution

Solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
"""Solution for the Leetcode Problem #0003 Longest Substring without Repeating Characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/
"""


def longest_substring_without_repeating_characters(s: str) -> int:
    """Given an input string `s`, return the length of the longest substring without repeating characters"""
    lengths = []

    previous_string = []
    for character in s:
        if character not in previous_string:
            previous_string.append(character)
        else:
            lengths.append(len(previous_string))
            previous_string = previous_string[previous_string.index(
                character)+1:]+[character]

    lengths.append(len(previous_string))

    return max(lengths) if len(lengths) > 0 else len(s)

This implementation uses what is called a Sliding Window Iterator This is used when there are problems using a substring.

Solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
"""Solution for the Leetcode Problem #0003 Longest Substring without Repeating Characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/
"""


def longest_substring_without_repeating_characters(s: str) -> int:
    """Given an input string `s`, return the length of the longest substring
    without repeating characters"""

    start = max_length = 0
    used_characters = {}

    for index, character in enumerate(s):
        if used_characters.get(character) is not None and start <= used_characters[character]:
            start = used_characters[character] + 1
        else:
            max_length = max(max_length, index - start + 1)

        used_characters[character] = index

    return max_length