Longest Substring Without Repeating CharactersMay 16 '11，

Longest Substring Without Repeating CharactersMay 16 '11，

Longest Substring Without Repeating CharactersMay 16 '11

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.

方法一：通过最简单粗暴的方法可以确定一个大致的复杂度范围<O(N^2)。

 

方法二：过一遍字符串，如果当前字符与目前无重复子串中的字母有重复，记录当前最大无重复子串长度，弃掉当前子串前一个重复字母及其之前的字符，添加当前字符，继续遍历过程。O(N)的复杂度。对于不仅仅有字母的字符串开一个256的记录数组（大小128的其实就够用了）。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    // Start typing your C/C++ solution below
     // DO NOT write int main() function
	if(s.length()==0) return 0;
	int max_sub_len = 0;
	char index[26];
	memset(index, -1, 26);
	int begin = 0;
	int end = 0;
        for(int i = 0 ;i < s.length();i++)
	{
		if(index[s[i]-'a']>=begin){
				
			begin = index[s[i]-'a']+1;				
		}
		index[s[i]-'a'] = i;
		end = i;
		max_sub_len = max(max_sub_len,end-begin+1);
	}
	return max_sub_len;
    }
};

 48 milli secs