3. Longest Substring Without Repeating Characters

1. Description

Given a string s, find the length of the longest substring without repeating characters.

Constraints:

1. \(0 \leq s.length \leq 5 \times 10^{4}\)
2. s consists of English letters, digits, symbols and spaces.

1.1. Examples:

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

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

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.

2. Solution

2.1. Understanding the problem

I think this is similar to two pointers where we maintain a fast_pos and a slow_pos.

The idea is that fast_pos moves.

2.2. Algorithm

2.3. Code

Listing 1: 3 Longest Substring Without Repeating Characters my solution

def lengthOfLongestSubstring(s):
    """
    :type s: str
    :rtype: int
    """

    slow_pos = 0
    fast_pos = 0
    max_length = 0

    while fast_pos < len(s):
        # we can still do one last comparison when fast_pos == len(s) - 1
        substring = s[slow_pos : fast_pos + 1]
        if len(substring) == len(set(substring)):
            max_length = max_length if max_length > len(substring) else len(substring)
        else:
            # note we can't just move slow_pos to fast_pos here
            # as that will break test case "dvdf"
            slow_pos += 1
        fast_pos += 1

    return max_length


# tests
s = ""
print(lengthOfLongestSubstring(s) == 0)

s = "b"
print(lengthOfLongestSubstring(s) == 1)

s = "bba"
print(lengthOfLongestSubstring(s) == 2)

s = "pwwkew"
print(lengthOfLongestSubstring(s) == 3)

s = "dvdf"
print(lengthOfLongestSubstring(s) == 3)

Listing 2: 3 Longest Substring Without Repeating Characters my solution-results

True
True
True
True
True

2.3.1. Complexity

2.3.1.1. Time complexity:

O(n)

2.3.1.2. Space complexity:

O(n), need the space for the substring.

2.4. Leetcode solution

nil.

Listing 3: 3 Longest Substring Without Repeating Characters leetcode solution

<<imports for typing>>

Listing 4: 3 Longest Substring Without Repeating Characters leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

3.1. General thoughts

I reckon this is almost a two pointers question.

Also Leetcode provides an interesting optimized solution.

3.2. Related problems

4. Log time