# lc3.Longest Substring Without Repeating Characters

Contents

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

Example 1:

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

Example 2:

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

Example 3:

 ``````1 2 3 4 `````` ``````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:

 ``````1 2 `````` ``````Input: s = "" Output: 0 ``````

Constraints:

• `0 <= s.length <= 5 * 104`
• `s` consists of English letters, digits, symbols and spaces.
##### Thinking

The simplest method to do is the brute force searching. Given a substring, we check whether it contains repeated characters. Then for all substrings of a given string, we do such a test and the total number of substrings of a given string with length \$n\$ is \$n*(n+1)/2\$.

For example, For each substring str[i, j] i.e. starting from index i and ending at index j, we use a function areUnique(str, i, j) to check if all the characters in the substring are unique or not. It will return true if all the characters are unique, otherwise false.

The time complexity of areUnque(str,i,j) is \$O(j-i+1)\$.

So the overall time compelxity is \$n*(n+1)/2*O(j-i+1)=O(n^2)*O(j-i+1)\$. In the worst-case, \$O(j-i+1)=O(n)\$, so the worst-case overall time complexity is \$O(n^3)\$.

We are using few extra variables and a constant size set visited[]. So space complexity = O(1).

To optimize, here is an optimization insight:

In the brute force idea, we repeatedly check a substring starting from the character str[i] to see if it has a duplicate character or not. We can optimize it further because, during the loop, if a substring str[i, j-1] is already checked to have no duplicate characters, then for the substring str[i, j], we only need to check if str[j] is already present in the substring str[i, j-1] or not.

Partially cited from: https://www.enjoyalgorithms.com/blog/longest-substring-without-repeating-characters

###### 暴力解法：
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ _max=0 for i in range(len(s)): sub=[s[i]] for j in range(i+1,len(s)): if s[j] not in sub: sub.append(s[j]) else: break if len(sub)>_max: _max=len(sub) return _max ``````

###### 滑动窗口解法：
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````class Solution: def lengthOfLongestSubstring(self, s): if not s:return 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > max_len:max_len = cur_len lookup.add(s[i]) return max_len ``````