LeetCode解析（三）： Longest Substring

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

Example:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

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.

难度：Medium

解析：寻找最长的无重复字母的子字符串。

方法一：穷举遍历（★★★）

遍历所有的子字符串，判断其是否含有相同的字母，如果不包含相同的字母，且将result不断更新为最大的符合条件的子字符串的长度

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

结果：Runtime: [Time Limit Exceeded]
备注：时间复杂度O(n^3)，显然这个操作很差。

方法二：Set筛选（★★★★）

取子串 [ i，j ]，子串中字符均在Set之中，取下一字符 s[ j+1 ]，如果Set不包含字符s[ j+1 ]，则取子串 [ i，j +1]，ans ++，继续取下一字符重复如上判断，如果Set包含字符s[ j+1 ]，则取子串 [ i+1，j ]，继续取字符 s[ j+1 ]重复如上判断，直至 j >= n 结束，ans 为最后的结果结果。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

结果：Runtime: 30 ms，beats 65.53% of Java submission.
备注：遍历数组，时间复杂度O(n)。

方法三：数组筛选（★★★★★）----所有用户提交通过的答案中的最佳方法之一

ASCII码，65 ~ 90代表[A，Z]，97~122代表[a，z]，数组index[]只需128位即可代表全部码值。
在数组index[]中，例如字符串“abcdefg”，其中“a”的ASCII码为97，位于字符串的第1位，故存于index[97] = 1，以此类推；

数字 i 记录的是字符最后一次出现的位置，当 i > 0时，i之前的子串必然会有和i重复的字符（ [0，i] 范围的子字符串的最大子串已保存于ans中），故只需考虑 i 之后的子串，即仅考虑 [i,j] 范围的子字符串，更新ans。

总而言之，即数字 i 记录每一次重复字符最新的位置，把原始字符串用 i 分为若干不重复的子字符串，用ans记录各个子字符串的大小。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        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;
    }
}

结果：Runtime: 16 ms.
备注：遍历数组，时间复杂度O(n)。