LeetCode算法题之第3题Longest Substring

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)时间复杂度的算法。在提交时会报运行超时的错误。

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;
}

那么有什么办法可以降低时间复杂度呢？一般来说，可以采用map或者set（set的内部代码使用了map）使得查找的时间复杂度从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;
}

上面的代码下标移动是一个一个来移动的。但是可以不用那么慢。如在abcdc12345的字符串中，当c重复时，下一步可以不从b开始，而从第一个c的后面一个开始，即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;
}

代码地址（附测试代码）：
https://github.com/shichaohao/LeetCodeUsingJava/tree/master/src/longestSubstringWithoutRepeatingCharacters