3. Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

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

Example 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.

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5*10^4
• s consists of English letters, digits, symbols and spaces.

Solution in python

1. Brute Force

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        i, j = 0, 0
        max_len = 0

        for i in range(len(s)):
            sol = set()
            j = i
            while j < len(s):
                if s[j] not in sol:
                    sol.add(s[j])
                    j += 1
                    if j - i > max_len:
                        max_len = j - i
                else:
                    if j - i > max_len:
                        max_len = j - i
                    break

        return max_len

2. Sliding window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        i = j = 0
        lensubstr = 1
        hashset = {}
        while i < len (s) and j < len(s):
            if s[j] not in hashset:
                hashset[s[j]] = j
                j += 1
                lensubstr = max(lensubstr, j-i)
            else:
                hashset.pop(s[i])
                i += 1

        return lensubstr