LeetCode - 3.Longest Substring Without Repeating Characters

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

Example 1:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 2:

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.

简单的滑动窗口写法：

由Map保存字符的索引，以双指针的方式一次遍历获得结果。

Runtime: 7 ms, faster than 90.45%.

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

虽然这是一个易于理解的写法，但很明显不是最有效率的。我又翻看了其他人的写法。

在LeetCode中文社区看到VioletKiss发布的：

通过String.indexOf(int ch, int fromIndex)方法来移动左指针。

Runtime: 2 ms, faster than 99.90%.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0;
        int left = 0;
        int length = 0;
        int result = 0;
        while (i < s.length()) {
            int pos = s.indexOf(s.charAt(i),left);
            if (pos < i) {
                if (length > result) {
                    result = length;
                }
                if (result >= s.length() - pos - 1) {
                    return result;
                }
                length = i - pos - 1;
                left = pos + 1;
            }
            length++;
            i++;
        }
        return length;
    }
}

以及英文官方发布的：

预设好Character的数组长度，通过数组记录每个Char出现的坐标。

Runtime: 2 ms, faster than 99.90%.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[256]; 
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}