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

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

给定一个字符串 s s s，找出其中不含有重复字符的最长子串的长度。

很容易想到时间复杂度为 O ( n 3 ) O(n^3) O(n3)的暴力算法：遍历 s s s的所有子串，使用集合判断每个子串是否有重复字符，在遍历过程中更新最大长度值。

public int lengthOfLongestSubstring(String s) {
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            Set set = new HashSet<>();
            boolean duplicate = false;
            for (int k = i; k <= j; k++) {
                if (set.contains(s.charAt(k))) {
                    duplicate = true;
                    break;
                }
                set.add(s.charAt(k));
            }
            if (!duplicate) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
}

事实上，我们无需遍历 s s s的所有子串。如果 s [ i ∼ j ] s[isim j] s[i∼j]有重复字符，则 s [ i ∼ j + 1 ] s[isim j+1] s[i∼j+1]， s [ i ∼ j + 2 ] s[isim j+2] s[i∼j+2]，…， s [ i ∼ l e n − 1 ] s[isim len-1] s[i∼len−1]都有重复字符，因此 j j j无需继续向后遍历。

基于以上分析，可以将暴力算法优化成 O ( n 2 ) O(n^2) O(n2)：

public int lengthOfLongestSubstring(String s) {
    int maxLen = 0;

    for (int i = 0; i < s.length(); i++) {
        Set set = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            if (set.contains(s.charAt(j))) {
                break;
            }
            set.add(s.charAt(j));
            maxLen = Math.max(maxLen, j - i + 1);
        }
    }

    return maxLen;
}

在以上算法中，当我们发现子串 s [ i ∼ j ] s[isim j] s[i∼j]有重复字符时，立即结束 j j j的向后遍历，然后将 i i i向前移动一个字符，并继续遍历 s [ i + 1 ∼ . . . ] s[i+1sim ...] s[i+1∼...]。

事实上，我们可以一次将 i i i向前移动多个字符，并保持 j j j不变。假设 s [ i ∼ j − 1 ] s[isim j-1] s[i∼j−1]无重复字符， s [ i ∼ j ] s[isim j] s[i∼j]有重复字符，则 s [ i ∼ j − 1 ] s[isim j-1] s[i∼j−1]中必然有一个字符 s [ k ] s[k] s[k]等于 s [ j ] s[j] s[j]。我们可以将 i i i直接移动到 k + 1 k+1 k+1处，此时 s [ k + 1 ∼ j ] s[k+1sim j] s[k+1∼j]无重复字符，又可以继续向后遍历 j j j。

使用这种方法，可以将算法的时间复杂度降低到 O ( n ) O(n) O(n)。

public int lengthOfLongestSubstring(String s) {
    Set set = new HashSet<>();
    int i = 0, j = 0, maxLen = 0;

    while (j < s.length()) {
        // j向右移动，直到s[i~j]有重复字符
        while (j < s.length() && !set.contains(s.charAt(j))) {
            set.add(s.charAt(j));
            j++;
        }

        // 此时s[i~j-1]无重复字符，更新最大长度
        maxLen = Math.max(maxLen, j - i);

        // j到达字符串末尾，无需继续搜索
        if (j == s.length()) {
            break;
        }
        
        // i向右移动，直到s[i] == s[j]
        while (s.charAt(i) != s.charAt(j)) {
            set.remove(s.charAt(i));
            i++;
        }

        // 删除set中的重复字符，i向前移动一位，此时s[i~j]重新回到无重复字符状态
        set.remove(s.charAt(i));
        i++;
    }

    return maxLen;
}

func lengthOfLongestSubstring(s string) int {
	set := map[uint8]bool{}
	i, j, maxLen := 0, 0, 0

	for j < len(s) {
		// j向右移动，直到s[i~j]有重复字符
		for j < len(s) {
			if _, exist := set[s[j]]; exist {
				break
			}

			set[s[j]] = true
			j++
		}

		// 此时s[i~j-1]无重复字符，更新最大长度
		maxLen = int(math.Max(float64(maxLen), float64(j-i)))

		// j到达字符串末尾，无需继续搜索
		if j == len(s) {
			break
		}

		// i向右移动，直到s[i] == s[j]
		for s[i] != s[j] {
            delete(set, s[i])
			i++
        }

		// 删除set中的重复字符，i向前移动一位，此时s[i~j]重新回到无重复字符状态
        delete(set, s[i])
		i++
	}

	return maxLen
}