3. Longest Substring Without Repeating Characters 不含重复字母的最长子串

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is"abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
给定一个字符串，找出其中不含重复字母的最长子串（注意不是子序列），返回它的长度。

---

思路
字母查重：构建一bool列表，存储当前子串中是否含有某字母。
设置两指针i和j，分别表示子串头尾，j向后扫描，每次进行查重，保存当前子串长度，遇重复字母则i移动到此字母第一次出现的下一个位置，并将移除子串的字母进行查重表更新。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i=0,j=0;
        int n=s.size();
        int maxlen=0;
        bool exist[256]={false};
        while(j<n){
            if(exist[s[j]]){
                maxlen=max(maxlen,j-i);
                while(s[i]!=s[j]){
                    exist[s[i++]]=false;
                }
                ++i;
                ++j;
            }
            else{
                exist[s[j++]]=true;
            }
        }
        maxlen=max(maxlen,n-i);
        return maxlen;
    }
};

也可使用HashMap存储字符出现的位置，若存在则取同一个字符两个位置的距离，若不存在则记录字符的位置。

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