无重复字符的最长子串

题目

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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。

示例 3:

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

分析

最开始想到的解法就是用str.substring(0,str.length-2)和str.substring(str.length-2,str.length-2)去判断前一个是否存在后一个元素中的值。如果存在递归，说明后一个元素重复。后一个元素重复也不能证明出什么结论，并且递归的去判断并不能推导出最长的子串。

官方思路

如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 k个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 kr。那么当我们选择第 k+1 个字符作为起始位置时，首先从k+1到 r_kr的字符显然是不重复的，并且由于少了原本的第 kk 个字符，我们可以尝试继续增大 r_kr，直到右侧出现了重复字符为止。

用图来表示就是：

代码示例

private static int lengthOfLongestSubstring(String s){
        //表示最长子串的长度
        int maxLength = 0;

        //索引
        int firstIndex = 0;
        int lastIndex = 0;
        HashMap<Character,Integer> map = new HashMap<>();
        //firstIndex、lastIndex都必须小于字符串长度
        while(firstIndex < s.length() && lastIndex< s.length()){
            //获取lastIndex指向的字符
            Character key = s.charAt(lastIndex);
            //判断字符是否存在map中
            if(map.containsKey(key)){
                //存在map中表明key元素已经和前面的字符串重复
                Character rKey = s.charAt(firstIndex);
                //移除当前字符串中的第一个元素
                map.remove(rKey);
                //起始点+1
                firstIndex++;
            }else{
                //如果不存在就将元素放到map中
                map.put(key,lastIndex);
                //lastIndex继续向前
                lastIndex++;
            }
            //最后如果本次得到的子串长度大于maxLength就进行替代
            maxLength = lastIndex -firstIndex>maxLength?lastIndex-firstIndex:maxLength;
        }
        return maxLength;
    }