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.

思路1：用HashSet

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s==null||s.length()==0){
            return 0;
        }

        HashSet<Character> set = new HashSet<Character>();
        int max = 0;
        int i = 0;
        int start = 0;
        for (i=0;i<s.length();i++){
            char c = s.charAt(i);
            if (!set.contains(c)){
                set.add(c);
            }else{
                max = Math.max(max,set.size());
                while(start<i&&s.charAt(start)!=c){
                    set.remove(s.charAt(start));
                    start++;
                }
                start++;
            }
        }

        max = Math.max(max,set.size());
        return max;
    }
}

思路2：超精简算法，just show show

public int lengthOfLongestSubstring(String s) {
    int i = 0, j = 0, max = 0;
    Set<Character> set = new HashSet<>();

    while (j < s.length()) {
        if (!set.contains(s.charAt(j))) {
            set.add(s.charAt(j++));
            max = Math.max(max, set.size());
        } else {
            set.remove(s.charAt(i++));
        }
    }

    return max;
}

C++ code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()||s.length()==0){
            return 0;
        }

        unordered_set<char> set;
        int maxVal = 0;
        int i = 0;
        int start = 0;
        for (int i=0; i<s.length(); i++){
            char c = s[i];
            if (set.find(c)==set.end()){
                set.insert(c);
            }else{
                int len = set.size();
                maxVal = max(len,maxVal);
                while(start<i && s[start]!=c){
                    set.erase(s[start]);
                    start++;
                }
                start++;
            }
        }
        int len = set.size();
        return max(len,maxVal);;
    }
};