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

电玩女神 2024-04-03 14:01 41阅读 0赞

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

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

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

> **示例 3:  
> 输入: s = “pwwkew”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。**

> **请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。**

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**采用滑动窗口法**

分析：

'''
    i=0
    j=0
    max=0
    
    
    abcabcbb
    i
       j
    
    {
       a:1
       b:1
    }
    
    max=
    return max
    
    '''

代码实现

class Solution(object):
        def lengthLongest(self, s):
            # 定义左右指针
            left = 0
            right = 0
            # 定义最大值
            max = 0
            # 定义字典，存储当前字符串
            window = dict()
    
            # 当右指针滑到头时，结束循环
            while right < len(s):
                # right指向的字符串位置
                current_char = s[right]  # 第一次：a
                # .setdefault()
                # 如果键不存在字典中，将会添加键并将值设为默认值0
                window.setdefault(current_char, 0)
                window[current_char] += 1  # 相当于把a定义成1
                # 往后走1位
                right += 1
    
                # 窗口中有重复的字符串时缩小窗口
                while window[current_char] > 1:
                    left_char = s[left]
    
                    # i往右移动1位
                    left += 1
    
                    # 更新字典中current_char的数量
                    window[left_char] -= 1
    
                # 临时获取字符串的长度
                window_size = right - left
    
                if window_size > max:
                    max = window_size
            return max
    
    
    s = "pwwkew"
    
    solution = Solution()
    res = solution.lengthLongest(s)
    print(res)