LeetCode Longest Substring Without Repeating Characters 最长不重复子串查找

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

这道题目也是下标难以处理，关键点：

1 利用maxlength变量记录当前已经查找到的最长不重复子串

2 巧妙的移动两个下标，如下图示：

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int n = s.length();
		int i = 0;
		int j = 0;
		bool found[26] = {false};
		int maxLength = 0;
		for (; i < n; i++)
		{
			if (!found[s[i] - 'a'])
			{
				found[s[i] - 'a'] = true;
			}
			else
			{
				maxLength = max(maxLength, i-j);
				//注意：这里是关键，i是等到第二次s[i]==s[j]的时候才往前进的，而且是始终指向前一次重复出现字母的后一个字母。
				while (s[i] != s[j])
				{
					found[s[j] - 'a'] = false;
					j++;
				}
				j++;
			}
		}
		maxLength = max(maxLength, n-j);
		return maxLength;
	}
};