Longest Substring Without Repeating Characters

无重复字符串最长字串

题目

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解析重点

1.我们可以滑动窗口i、j，窗口覆盖的即为字串。当滑动到下一个字符时，如果当前字符出现过，1.当前字符在滑动窗口外，则无影响。2.当前字符出现在滑动窗口内，
则出现了重复，起始位置重置为当前字符前一次出现的位置+1，即s.charAt(j)+1

java代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n=s.length(),nas=0;
        Map<Character,Integer> map = new HashMap<>();
        for(int j=0,i=0;j<n;j++){//i->子串起始位置，j->子串结束位置
            if(map.containsKey(s.charAt(j))){//判断当前字符是否出现过
                i=Math.max(map.get(s.charAt(j))+1,i);//如果当前字符出现过，1.当前字符出现的位置在i前面，则i不变，
                                                     //2.当前字符出现的位置在i后面，则重置起始位置为s.charAt(j)+1
            }
            nas=Math.max(nas,j-i+1);//比较历史字串和当前窗口串的大小
            map.put(s.charAt(j),j);//当前位置索引放入hashmap
        }
        return nas;
    }
}