3. Longest Substring Without Repeating Characters

🟨 Medium

Question

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

Example 1:

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

Example 2:

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

Example 3:

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

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

def lengthOfLongestSubstring(self, s: str) -> int:
    n = len(s)
    if n < 2: #no prepeating word when n < 2
        return n 
    res, tmp = "", "" #init result and tmp substring
    for i, c in enumerate(s):
        if c not in tmp: #simply add char if not include
            tmp += c
        else:
            idx = tmp.find(c) #find index of char in tmp
            tmp = tmp[idx+1:] + c
        res = tmp if len(tmp) > len(res) else res
    return len(res)