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 * 104s consists of English letters, digits, symbols and spaces.
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
longest = 0
d = {}
start = 0
for i, c in enumerate(s):
if c in d and d[c] >= start:
start = d[c] + 1
d[c] = i
longest = max(longest, i - start + 1)
return longest
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func lengthOfLongestSubstring(s string) int {
ans := 0
m := make(map[byte]int) // "last occurred" map
i := 0
for j, v := range []byte(s) {
if v, ok := m[v]; ok && v > i {
i = v
}
// e.g.
// "a": i=0, j=0, len is 0-0+1=1
// "ab": i=0, j=1, len is 1-0+1=2
// "aba": i=1, j=2, len is 2-1+1=2
if j - i + 1 > ans {
ans = j - i + 1
}
m[v] = j + 1
}
return ans
}
|