[LeetCode]Longest Substring Without Repeating Characters

Sliding window的做法，动态地维护左右边界，策略如下：

• 如果当前c没有见过，插入map
• 如果见过，pop左边界对应的字符直到满足no repeating char的条件

这样的话，对于所有i，我们找到的是最长的以i为右边界的no repeating char的区间。时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int lengthOfLongestSubstring(string s) {
	int len = s.size(), maxLen = 0, left = 0;
	unordered_set<char> set;
	for(int i = 0; i < len; ++i)
	{
	if(set.find(s[i]) != set.end())
	{
	while(true)
	{
	char c = s[left++];
	set.erase(c);
	if(c == s[i])break;
	}
	}
	set.insert(s[i]);
	maxLen = max(maxLen, i - left + 1);
	}
	return maxLen;
	}
	};

view raw Longest Substring Without Repeating Characters.cpp hosted with ❤ by GitHub