3. Longest Substring Without Rep

Description

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.

Code

1. 暴力解法
   思路
   枚举所有子串，逐一判断每一子串是否是无重复子串，如果是无重复子串，则与当前已知的最长的无重复子串比较，如果比其更长，则需要更新子串长度

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        // i 是子串的起点，j - 1 是子串的终点
        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;
    }

    // 用 set 来判断是否有重复元素
    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;
    }
}

时间复杂度： O(n ^ 3)
空间复杂度：set 的大小

2. 滑动窗口(两根指针的前向型应用)
   思路
   如果 i 到 j-1 没有重复元素，则当 j++ 后只需判断 j 位置元素是否在 i 到 j-1 出现过，无需重复判断i 到 j-1 中是否有重复元素，而用一个 set 就可以在 O(1) 的时间内判断出 s.charAt(j) 是否出现过

public 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++));
                // j 在添加到 set 后又执行了一次 j++ 操作
                // 所以本来的 j - i+ 1的写法就变成了 j - i
                // 滑动窗口范围从 i 到 j - 1 并不包含 j
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

时间复杂度：O(2n) 近似于 O(n)
空间复杂度：O(k) k 为 set 大小

3. 用 HashMap 优化滑动窗口
   思路
   以字母为键，下标为值，建立哈希表，如果 s[ j ] 在[ i, j ) 范围内有有和它一样的重复字母s[ j' ]， 则 i 可以直接跳过 [ i, j' ] 范围内的所有元素，直接从 j' + 1 开始，优化了滑动窗口一点点移动 i 的做法

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        // current index of character
        Map<Character, Integer> map = new HashMap<>();
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            // j 从 0 开始，区间范围 [i, j)，所以要对应 j + 1；
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

4. Assuming ASCII 128
   思路
   在时间复杂度最优的情况下，考虑构成字符串的字母集，字母集比 hash 表要小得多，利用字母集取代 hash 表来达到优化空间复杂度的目的
   定义数组：
   1. int[26] for Letters 'a' - 'z' or 'A' - 'Z'
   2. int[128] for ASCII
   3. int[256] for Extended ASCII

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