一、无重复字符的最长子串

1、问题

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

示例 4:

输入: s = “”
输出: 0

提示：

• 0 <= s.length <= 5 * 10⁴
• s 由英文字母、数字、符号和空格组成

2、思路

1. 创建一个字典map,用来存储“字符”及“字符位置下标+1”（加 1 表示从字符位置后一个才开始不重复）。
2. 定义不重复子串的开始位置为 start，结束位置为 end,初始化为 0。
3. 定义一个变量 ans，用来记录“无重复字符子串”的长度。
4. 遍历字符串 s , 遍历结束条件为 end < 字符串长度 。
5. 如果遍历到的字符在map中，此时将“该字符”作为 key 值，在map中获取其 value 值，与原start进行对比取最大值，并更新 start，更新后此时 [start, end] 区间内不存在重复字符。
6. 无论是是否需要更新start，都需要将遍历到的字符添加到map中，并更新ans。
7. 遍历结束返回ans。

3、代码

#coding:utf-8
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start,end,ans,n,map= 0,0,0,len(s),{}
        while end < n:
            if s[end] in map:
                start = max(map[s[end]],start)
            map[s[end]] = end + 1
            ans = max(end - start + 1, ans)
            end += 1
        return ans

if __name__ == "__main__":
    # s = "abcabcbb"
    # s = "bbbbb"
    # s = "pwwkew"
    # s = ""
    # s = "dvdf"
    s = "abba"

    print(Solution().lengthOfLongestSubstring(s))

4、时间与空间复杂度

时间复杂度：O(n)
n为字符串长度

空间复杂度：O(∣Σ∣)
Σ表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小

备注

1、问题来自：
力扣（LeetCode）
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

2、参考：
guanpengchn
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/