求字符串不重复子串的最大长度

问题描述

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

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

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

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

解题思路

对字符串进行一次遍历，每遍历一个字符求一次最大字串长度。

• 设置滑动窗口，定义窗口起始位置变量用于保存窗口起始位置，窗口结束位置即为当前遍历字符的位置。
• 若当前遍历字符在窗口中，修改窗口起始变量
• 若当前遍历字符串不在窗口中，根据窗口大小更新最大字串长度。
• 字符串遍历结束，返回最大字串长度
  

Python实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 保存最大字串长度
        res = 0
        # 保存窗口起始位置
        start = 0
        for idx,ch in enumerate(s):
            # 判断当前字符是否在窗口内
            if ch in s[start:idx]:
                # 若当前字符在窗口内，更新起始位置
                start = s[start:idx].index(ch) + start + 1
            else:
                # 若当前字符不在窗口内，更新最大字串长度
                res = max(res,idx+1-start)
        return res