【D16】无重复字符的最长子串（LC 3）

3. 无重复字符的最长子串

问题描述

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

解题思路

读题之后想用动态规划来解决，但是看到s.length <= 5 * 10^4时，经验告诉我，动态规划很可能超出时间/空间限制。
于是开始思考用双指针来解题。固定左指针，移动右指针；当右指针移动时，遇到了重复的字符，则将左指针向右移动至右侧重复字符的下一个字符，若重复字符在此时left的左侧，则左指针不移动；这样就保证了左右指针之间的字符一定是无重复字符。

代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), left = 0, res =0;
         //hashmap,key为字符，value为该字符在s中的索引值
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();

        for(int i = 0; i < s.length(); i ++){
            Character c = s.charAt(i);
            //如果右指针移动时，遇到了重复的字符，则将左指针移动至重复字符的下一个字符
            if(map.containsKey(c)){
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c,i);
            //不断更新无重复字符子串的最大值
            res = Math.max(res, i-left+1);
        }
        return res;
    }
}