3. 无重复字符的最长子串

Posted on | In
Words count in article: 789 | Reading time ≈ 3

题目

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

示例1:

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

示例2:

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

示例3:

1
2
3
4
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.

解法

解法一：

暴力破解

取该字符串的每一个连续字串，判断其是否为该字符串的最长字串。先从长度为n的子字符串开始，如果符合条件的话，直接返回n；否则从2个n-1长度的字串中，选择，以此类推。时间复杂度O(n*n*n)

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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判断当前字符串是否不重复，如果不重复的话，则往右再扩一位，重复的话，则把当前窗口再顺移一位。

JAVA

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

拿字符串“aabbcd”举例来说。

窗口左坐标 窗口右坐标 当前不重复的字符集 最大不重复子字符串长度 备注
初始化 0 0 空 0
加入a 0 1 a 1
再次加入a 1 1 空 1
再次加入a 1 2 a 1 此处是因为j的值没有自增，所以index为1的a，会再被加入依次
加入b 1 3 a,b 2
再次加入b 2 3 b 2
再次加入b 3 3 空 2
再次加入b 3 4 b 2 同上，因为j没有更新值，index为3的b会被加入多次
加入c 3 5 b，c 2
加入d 3 6 b，c，d 3

解法三：

滑动窗口优化版

在解法二中，每当碰到相同的值的时候，我们总是把窗口左坐标一步一步地往后移，其实，这里面存在优化的空间。比如，在区间[i, j)中，某个元素重复了，假设重复的那个索引为k，那么，我们就可以直接跳过[i,k]这段区间，直接从k+1,开始计算。

JAVA

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

参考资料

https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/

0%