题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

题解一

采用滑动窗口的思想，初始窗口大小为1，判断窗口内是否有重复字符，若不含重复字符，则更新最大窗口，并在右边扩大窗口。若窗口内含有重复字符，则在左边收缩窗口。

这种方法需要 $O(n)$ 的时间遍历滑动窗口，还需要 $O(n)$ 的时间检查滑动窗口内是否含有重复字符。

总的时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。

以字符串"arabcacfr"为例，初始化最大窗口为1，此时窗口内字符串为"a"，不含重复字符，则最大窗口为1，窗口右边扩大；
此时窗口内字符为"ar"，不含重复字符，最大窗口为2，窗口右边扩大；
此时窗口内字符为"ara"，含重复字符，窗口左边收缩；
此时窗口内字符为"ra"，不含重复字符，最大窗口为2，窗口右边扩大；
此时窗口内字符为"rab"，不含重复字符，最大窗口为3，窗口右边扩大；
此时窗口内字符为"rabc"，不含重复字符，最大窗口为4，窗口右边扩大；
此时窗口内字符为"rabca"，含重复字符，窗口左边收缩；
此时窗口内字符为"abca"，含重复字符，窗口左边收缩；
此时窗口内字符为"bca"，不含重复字符，最大窗口为4，窗口右边扩大；
此时窗口内字符为"bcac"，含重复字符，窗口左边收缩；
此时窗口内字符为"cac"，含重复字符，窗口左边收缩；
此时窗口内字符为"ac"，不含重复字符，最大窗口为4，窗口右边扩大；
此时窗口内字符为"acf"，不含重复字符，最大窗口为4，窗口右边扩大；
此时窗口内字符为"acfr"，不含重复字符，最大窗口为4，窗口右边扩大；
结束，返回最大窗口4。

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0)
        return 0;
    int maxWindow = 1;
    int left = 0, right = 1;
    while (right < s.length()) {
        String window = s.substring(left, right+1);
        if (examineHelper(window)) {
            maxWindow = Math.max(maxWindow, right-left+1);
            right++;
        }
        else left++;
    }
    return maxWindow;
}

private boolean examineHelper(String s) {
    HashSet<Character> set = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        if (!set.contains(s.charAt(i)))
            set.add(s.charAt(i));
        else return false;
    }
    return true;
}

题解二

上面的滑动窗口仍然可以进行改进，我们可以使用HashSet作为滑动窗口，这样可以在 $O(1)$ 的时间内完成对字符串内重复元素的检查，从而将时间复杂度降低到 $O(n)$ 。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0)
        return 0;
    int maxWindow = 0, left = 0, right = 0;
    HashSet<Character> set = new HashSet<>();
    while (right < s.length()) {
        if (!set.contains(s.charAt(right))) {
            set.add(s.charAt(right++));
            maxWindow = Math.max(maxWindow, right-left);
        } else set.remove(s.charAt(left++));
    }
    return maxWindow;
}

题解三

题解二中的滑动窗口最多仍然需要执行 $2n$ 个步骤，我们可以使用HashMap记录字符的位置，而不是仅仅判断字符是否存在。这样，在找到重复元素的时候就可以在更新滑动窗口的时候直接跳过这个元素。也就是说，我们不需要逐渐增加 $left$ 的值，而是可以将滑动窗口的 $left$ 直接更新到上一个重复元素的后面。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0)
        return 0;
    int maxWindow = 0, left = 0, right = 0;
    HashMap<Character, Integer> map = new HashMap<>();
    while (right < s.length()) {
        if (map.containsKey(s.charAt(right)))
            left = Math.max(left, map.get(s.charAt(right)) + 1);
        map.put(s.charAt(right), right++);
        maxWindow = Math.max(maxWindow, right-left);
    }
    return maxWindow;
}