Longest Substring Without Repeating Characters——Sliding Window, Hash Table

题目

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中有讨论提到与KMP算法类似，但本质思想上是不同的。在KMP算法中是通过PMT的数组——next数组来实现字符串匹配的。next数组中的值是子字符串的前缀集合与后缀集合的交集中最长元素的长度，通过next数组使字符串匹配算法能够利用到已经匹配部分的子字符串信息，从而加快匹配速度。代码如下：

int KMP(char * t, char * p) 
{
	int i = 0; 
	int j = 0;

while (i < strlen(t) && j < strlen(p))
{
	if (j == -1 || t[i] == p[j]) 
	{
		i++;
          		j++;
	}
 	else 
          		j = next[j];
   	}

   if (j == strlen(p))
      return i - j;
   else 
      return -1;
}

而题目中的滑动窗口移动的目标不是KMP中利用next数组找到与子字符串已匹配的最长后缀长度从而简化字符串匹配过程，而是将滑动窗口中的重复字符删除。
其中next数组的计算代码为：

void getNext(char * p, int * next)
{
	next[0] = -1;
	int i = 0, j = -1;

	while (i < strlen(p))
	{
		if (j == -1 || p[i] == p[j])
		{
			++i;
			++j;
			next[i] = j;
		}	
		else
			j = next[j];
	}
}

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> substring;
        int begin = 0, end = 0, max_length = 0, n = s.size();
        while(end < n){
            while(substring.count(s[end])){
                substring.erase(s[begin]);
                begin++;
            }
            max_length = max(max_length, end - begin + 1);
            if(!substring.count(s[end])){
                substring.insert(s[end]);
                end++;
            }

        }
        return max_length;
    }
};

参考：https://www.zhihu.com/question/21923021/answer/281346746