最大不重复子串思路解析

发表于 | 分类于

这个一个比较经典的考题，恰巧我在面试中也遇到了，现在把它写下来记录一下，原题的描述是这样的，下面是 LeetCode 的原文：

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.

解题思路：

HashMap

基本思路：创建一个 HashMap，字符串中的字符作为 key 值，相应的其出现的位置作为 value 值；创建两个指针 i 和 j ，这两个指针决定了最大子串的长度，i 是左指针，j 是右指针；移动右指针去扫描字符串，同时更新 hashmap，如果这个字符已经出现过(已经在 hashmap 中)，那么将左指针移动到同一个字符最后一次出现的地方，也就是右指针当前的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;
        int max = 0;
        int len = s.length();
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i = 0,j = 0;i < len;i++){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i - j + 1);
        }
        return max;
    }
}

Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public 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;
    }
}

HashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

Array

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}