首页 > 代码库 > 【leetcode】 Longest Substring Without Repeating Characters

【leetcode】 Longest Substring Without Repeating Characters

题目:

给定一个字符串,返回该串没有重复字符的最长子串。

分析:

1)子串:子串要求是连续的。
2)无重复,出现重复就断了,必须从的位置开始。而新的位置就是重复字符第一次出现位置的下一个位置。
3)整个串可能没有一处重复。

那么,为了找出当前访问的字符是否出现过,要怎么做呢?当然是hash,O(1)的时间,而且既然是字符, 定义个255的hash table 就可以了,hash table 中的元素为相应字符在s中出现的位置。初始化为-1,表示都没有出现。
我们另外定义一个start 和end变量,来记录当前不重复子串的起始点,再定义一个记录最长子串的max_len变量,当当前不重复子串的长度大于最大值时,更改其值。

看个例子:

初始时 start = end = 0,随着end的移动,将遇到的字符的index加入到hash table 中,直到end = 3 的时候,发现 hash[ s[ end ] ] != -1,说明字符 b 在前面出现了,也就是说出现了重复,那么此时我们记录当前不重复的子串的长度 = end - start = 3 , 也就是abc子串。将该值3与max_len进行比较,更新max_len 的值。
那么此时start 的值应该怎么更新是最终要的,图中我们将其更改为2,这是怎么得来的呢?因为子串要求是连续的,当end = 3出现重复时,说明从 0 开始的s最长无重复子串的长度就是 3,因为不允许跳过这个重复的b继续向后进行,所以,更长的子串肯定只能出现在第一个b字符的后一个字符为起始点的情况。
hash table的处理是将新 start前的元素清除,即改为 -1 ,同时保存从新start 到end间的信息。这样end 走到最后就完成了。

实现:

int lengthOfLongestSubstring(string s) {
	int len = s.size();
	if(len <= 1)
		return len;
	//hash_table,record the index of items in s
	int hash_table[255];
	//-1 means haven't occur  
	memset(hash_table, -1, sizeof(hash_table));

	int start = 0;
	int end = 0;
	int max_len = 0;
	while(end < len)
	{
		char c = s[end];
		if(hash_table[c] == -1)
				hash_table[c] = end++;
		else
		{
			max_len = max(max_len, end - start);
			//new start
			start = hash_table[c] + 1;
			//clean items in hash_table .
			memset(hash_table, -1, sizeof(hash_table));
			//record the index of items from new start to end.
			for(int i = start; i <= end; ++i)
				hash_table[s[i]] = i;
			++end;
		}
	}
	//may be the s without repeating character from start to end.
	max_len = max(max_len, end - start);
	return max_len;
}