算法连载之求解不含有重复字符的最长子串长度

问题

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

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

暴力求解

枚举所有字符子串，获取长度最长的无重复字符子串。

分析程序，匹配在给定字符串中是否有重复字符isRepeating函数的时间复杂度是O(n)。因此，完成算法的时间复杂度是O(n³)；空间复杂度是O(min(n, m))，其中n是字符串的长度，m是相异字符的数量。

从算法分析，如果从 0 到 j-1 是无重复字符子串，第j项元素同前面的任意一个元素重复，则不管第j项后面有无元素，0<=j-1

滑动窗口求解

1）如果从 0 到 j-1 是无重复字符子串，第j项元素同前面的任意一个元素重复，则不管第j项后面有无元素，0<=j-1

2）移动开始索引位置，直到没有重复元素为止，此时为没有重复元素的子串，第j项作为结束索引继续向后移动，直到待判断的字符串结束为止，判断是否出现重复。如果出现重复，则继续重复2）。

滑动窗口算法优化了暴力求解法，当结束索引到第j项出现重复，不再向后继续判断，而是移动开始索引，直到没有重复元素为止，再继续向后移动结束索引，避免冗余判断。

在最坏情况下，字符串所有元素都会被开始索引和结束索引各遍历一次。时间复杂度是O(2n)=O(n)。空间复杂度是O(min(n, m))，其中n是字符串的长度，m是相异字符的数量。

分析算法发现，当出现一次重复时，我们移动开始索引位置，直到剔除重复元素为止。如果在移动过程中，未剔除重复元素，则一直要移动开始索引。因此，我们可以考虑让开始索引移动位置一步到位。

优化滑动窗口求解

优化滑动窗口求解方法，当出现判断字符为重复项时，直接将窗口的开始索引位置置于重复项的下一个元素继续判断。

时间复杂度是O(n)。空间复杂度是O(min(n, m))，其中n是字符串的长度，m是相异字符的数量。

性能分析

随机5000个字符的待匹配字符串进行测试：

The length of longest substring is 42 by Violence solve, using time is 2908 milliseconds.

The length of longest substring is 42 by Sliding Window solve, using time is 2 milliseconds.

The length of longest substring is 42 by Optimizing Sliding Window solve, using time is 2 milliseconds.

通过测试结果分析，移动窗口算法性能优异，时间复杂度是线性增长。