动态规划-滑动窗口-面试题48. 最长不含重复字符的子字符串

 动态规划：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer>dic=new HashMap<>();
        int i=-1,res=0;
        for(int j=0;j<s.length();j++){
            if(dic.containsKey(s.charAt(j)))
                i=Math.max(i,dic.get(s.charAt(j)));
            dic.put(s.charAt(j),j);
            res=Math.max(res,j-i);    
        }
        return res;
    }
}

滑动窗口 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        head=0
        tail=0
        if len(s)<2:  return len(s)
        res=1
        while tail<len(s)-1:
            tail += 1
            if s[tail] not in s[head:tail]:
                res=max(tail-head+1,res);
            else:
                while s[tail] in s[head:tail]:
                    head+=1    
        return res

参考博客链接：

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/tu-jie-hua-dong-chuang-kou-shuang-zhi-zhen-shi-xia/