LeetCode.003.Longest Substring Without Repeating Characters 最长非重复子串

题目描述

003 Longest Substring Without Repeating Characters
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

Example 1:

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

Example 2:

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

Example 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.

---

相似题目

LeetCode.076.Minimum Window Substring 最小覆盖子串
LeetCode.003.Longest Substring Without Repeating Characters 最长非重复子串
LeetCode.209.Minimum Size Subarray Sum 长度最小的子数组

---

解题过程

最长连续不重复子串问题：从一个字符串中找到一个连续子串，该子串中任何两个字符不能相同，求子串的最大长度。

O(n^3)穷举法

穷举法非常耗时间，即便用集合来判断是否有重复也还需要O(n^3)：

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

这是LeetCode Solution中给出的代码，allUnique()方法用哈希集合实现了O(n)判断是否有重复字符，才使复杂度降为O(n^3)，否则这道题穷举法就是O(n^4)的复杂度。

使用Map的O(n)方法2018

我自己也想到了用Map的O(n)方法，当前子串放到Map中，每次遇到新字符判断是否重复，有重复则更新最大子串长度并从重复字符的下一个位置重新开始：

public int lengthOfLongestSubstring(String s) {
    int max = 0;
    int len = 0;
    String maxSub = "";
    String sub = "";
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < s.length(); ) {
        if (map.containsKey(s.charAt(i))) {
            max = len > max ? len : max;
            maxSub = sub.length() > maxSub.length() ? sub : maxSub;
            len = 0;
            sub = "";
            i = map.get(s.charAt(i)) + 1;
            map.clear();
        } else {
            map.put(s.charAt(i), i);
            sub += s.charAt(i);
            len++;
            i++;
        }
    }
    max = len > max ? len : max;
    maxSub = sub.length() > maxSub.length() ? sub : maxSub;
    System.out.println(maxSub);
    return max;
}

调试几次提交后倒是通过了，但非常慢，只打败了1.8%的代码。而且虽然我写出来了，但思路不是很清晰，我自己也还有点不清楚这个方法到底对不对。

使用Set的O(n)方法

然后看Solution，这道题的Solution写的还是非常详细而全面的，给出的几种方法都很好。
有一种使用HashSet的O(n)方法，使用Set存储当前 滑动窗口[i,j) 中的元素，j不断右移，遇到和当前集合中重复的字符则停止，更新最大子串长度，也就是从i开始的最长不重复子串，然后i加1继续找从i+1开始的最长不重复子串。

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

为什么每次更新滑动窗口左边界i后(即从集合中删除s[i])，右边界j不需要回退呢？因为从i到j-1组成的子串我们已经验证过没有重复元素(否则右边界也走不到j)，所以右边界不用回退。
其实右边界j保持不动时，左边界i会一直增长到i’+1（i’是滑动窗口中和j重复的元素位置），因为对于以[i,i’]中的字符开头以j结尾的子串，肯定会有字符和和s[j]重复。基于这一点，我们可以对此方法再进行优化：每次出现重复字符后，i直接跳到i’+1的位置。

使用Map的O(n)方法

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

此算法比上一个使用集合的算法的优化就在于：每次出现重复字符后，左边界直接跳到重复字符后一位置。

2020年第二次解

2020 年 1月份的时候刚开始复习，做这道题感觉思路还是有点儿乱，5月份 LeetCode 每日一题遇到再写了一遍，感觉已经比较清晰了。
但我这个解法并不完全算是滑动窗口，因为每次发生重复后，我直接把窗口的长度归零了，复杂度较高。
用一个 map 保存保存窗口内的元素，发生重复时，从重复位置的下一个位置重新开始，此时我把窗口长度归零了，也就是右边界也清除了。
根据题解，此时右边界是不需要动的，只把左边界右移即可。

private static class SolutionV202005 {
    public int lengthOfLongestSubstring(String s) {
        if (null == s || s.length() < 1) {
            return 0;
        }
        int max = 0;
        // map 保存窗口内的元素，字符 -> 下标
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length;) {
            Character character = new Character(chars[i]);
            if (!map.containsKey(character)) {
                map.put(character, i);
                max = Math.max(max, map.size());
                i++;
            } else {
                // chars[i]和当前滑动窗口内字符重复，则下次滑动窗口从重复位置的下一个重新开始
                i = map.get(character) + 1;
                map.clear();
            }
        }
        return max;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_003_LongestSubstringWithoutRepeatingCharacters.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_003_LongestSubstringWithoutRepeatingCharacters.java

---