最长无重复子字符串

发表于 | 分类于

给一个字符串，找出最长的非重复子字符串长度
例如：
输入：”abcabcbb”
输出：3
答案是”abc”，所以长度为3

方法一：暴力穷举

这种方法思路比较简单，就是循环遍历整个字符串，依次找出最开始的非重复子字符串，然后得到其中的最大值进行返回。
以下是我当时使用暴力穷举法的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        for(int j = 0; j < s.length(); j++){
            String subS = s.substring(j);
            int lenOfFirS = lengthOfLeadingSubstring(subS);
            if(lenOfFirS > res){
                res = lenOfFirS;
            }
        }
        return res;
    }
    
    public int lengthOfLeadingSubstring(String s){
        for(int i = 0; i < s.length(); i++){
            String subS = s.substring(0,i+1);
            if(isRepeat(subS)){
                return subS.length() - 1;
            }
        }
        return s.length();
    }
    
    public boolean isRepeat(String s){
        char[] cArr = s.toCharArray();
        Set<Character> setS = new HashSet<Character>();
        for(int i = 0; i < cArr.length; i++){
            setS.add(cArr[i]);
        }
        return setS.size() != cArr.length;
    }
}

在leetcode的官方solution中，暴力穷举法的代码如下：

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

相对而言比我的代码更为简洁。

复杂度分析：
时间复杂度：$O(n^3)$
空间复杂度：$O(min(n,m))$

方法二：滑动窗口法

滑动窗口法在数组或者字符串中的问题中是一种十分普遍的算法，窗口范围通常是由数组（或字符串）的某一个开始位置和另一个结束位置定义的，例如，窗口$[i,j)$（左闭右开）。
窗口一般是朝一个方向移动，例如，我们将窗口$[i,j)$向右边移动一个元素，则窗口现在为$[i+1,j+1)$
对于我们的问题，我们可以使用HashSet来存储我们的窗口（字符集）$[i,j)$（初始位置$i=j$），然后我们向右移动$j$直到新增的元素在原来的窗口（HashSet）中存在或者移动到最右边。完成后，我们就得到了开始位置为$i$的最大不重复窗口，如果我们遍历所有的$i$，取最大值就是答案。

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

复杂度分析：
时间复杂度：$O(2n) = O(n)$，最坏情况是遍历所有的$i$和$j$。
空间复杂度：$O(min(n,m))$

方法三：优化滑动窗口法

我们可以使用Map来存储字符串以及它的索引位置，然后当我们发现有重复的字符时我们可以跳过中间的所有字符。
因为如果$s[j]$（表示$s$的第$j$到最后字符串）在位置$j’$有字符与窗口$[i, j)$中重复，则我们无需一个位置一个位置增加$i$，而是可以直接跳过$[i, j’]$中的所有元素。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // 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);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}