Question:

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.

解決：

首先可以很顯然地得到O(n^3)時(shí)間復(fù)雜度的算法。在提交時(shí)會(huì)報(bào)運(yùn)行超時(shí)的錯(cuò)誤。

public int lengthOfLongestSubstring(String s) {
    int maxLength = 0;
    int length2 = s.length();
    int index = -1;
    int j = 0;
    for (int i = 0; i < length2;){
        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(i));
        for (j = i + 1; j < length2; ++j){
            index = sb.indexOf("" + s.charAt(j));
            if (index == -1)
                sb.append(s.charAt(j));
            else
                break;
        }
        if (sb.length() > maxLength)
            maxLength = sb.length();
        i = i + index + 1;
        if (j == length2)
            break;
    }
    return maxLength;
}

那么有什么辦法可以降低時(shí)間復(fù)雜度呢？一般來說，可以采用map或者set（set的內(nèi)部代碼使用了map）使得查找的時(shí)間復(fù)雜度從O(n)降為O(1)。因此得到以下代碼：

public int lengthOfLongestSubstring(String s) {
    int maxLength = 0;
    int length = s.length();
    int left = 0, right = 0;
    HashSet<Character> hashSet = new HashSet<>();
    while(left < length && right < length){
        if (hashSet.contains(s.charAt(right))){
            hashSet.remove(s.charAt(left++));
        }else{
            hashSet.add(s.charAt(right++));
            maxLength = Math.max(maxLength, right - left);
        }
    }
    return maxLength;
}

上面的代碼下標(biāo)移動(dòng)是一個(gè)一個(gè)來移動(dòng)的。但是可以不用那么慢。如在abcdc12345的字符串中，當(dāng)c重復(fù)時(shí)，下一步可以不從b開始，而從第一個(gè)c的后面一個(gè)開始，即d。因此需要記錄字符的位置，采用了map。代碼如下：

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

代碼地址（附測(cè)試代碼）：
https://github.com/shichaohao/LeetCodeUsingJava/tree/master/src/longestSubstringWithoutRepeatingCharacters