30 Jun 2024
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.
Constraints:
0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.使用两个指针，一个指向子字符串的左边界，一个指向子字符串的右边界(需要left和right两个指针，指针的值是字符在字符串中的下标)
新增元素时，判断字符是否在子字符串中(s[right]是否在s[left,right]中)
若存在，需要更新左边界为字符上次出现下标+1(所以需要一个哈希数据结构，以字符为key，以字符在字符串中下标为值;另外，更新左边界时，会跳过合法字符的值，所以还需要对比左边界和存在字符index的大小，比左边界小的可以忽略)
每次循环，无论何种情况，都需要将新增字符在哈希数据结构中的下标更新；也需要更新合法子字符串的长度结果
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ans: int = 0 sw: Dict[str, int] = {} left: int = 0 for right in range(len(s)): cur = s[right] if cur in sw and sw[cur] >= left: left = sw[cur] + 1 sw[cur] = right ans = max(ans, right - left + 1) return ans