最长不含重复字符的子字符串

题面

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
示例

输入: "pwwkew"
输出: 3

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

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/zui-chang...

分析

  • 滑动窗口
  • 双指针
  • 哈希映射

上码

  • 哈希检测到是否有相同值
  • 无重复值,当前字符收录入哈希,右指针扩张
  • 有则,右指针等待扩大边界,左指增长,同时哈希收缩
  • 重复直到同值左侧耗尽,一轮循环时记录最大长度,本质 字典模拟双端队列
func lengthOfLongestSubstring(s string) int {
    maxLen := 0
    m := make(map[byte]struct{},0)
    for left,right := 0,0; right < len(s); {
        if _,ok := m[s[right]];ok {
            delete(m, s[left])
            left++
        }else{
            m[s[right]] = struct{}{}
            right++
        }
        if right - left > maxLen {
            maxLen =  right - left
        }
    }
    return maxLen
}

小结

循环体内自增,可让边界在循环体内参与计算,合理避免越界
同队列,栈一样,哈希变量动态扩张与收缩,可作为临时辅助工具参与

本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
133
粉丝
24
喜欢
100
收藏
54
排名:107
访问:8.9 万
私信
所有博文
社区赞助商