LeetCode: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.

Solution:
今天做的两道题都是关于双指针问题
刚开始尝试用DP，无果，后来参考解释，有了这个思路
这个题的解法稍微容易一些，用一个数组保存已经出现的字符信息，下标是某个letter的ASCII码值
重点是发现重复字符后的处理：1.比较是否找到更长的符合条件的字符串，2，suppose, s[j]==s[i] (j>i), then set letterExist[start...i-1] to false, the next potential substring starts from i+1; 下面这个图不错，转过来

Code:

	public int lengthOfLongestSubstring(String s) {
	if(s==null||s.length()==0) return 0;
	boolean[] letterExist=new boolean[256];
	int start=0;
	int maxLen=0;
	int i=0;
	for(i=0; i<s.length(); i++){
	if(letterExist[s.charAt(i)]){//find a repeated char at i
	if(i-start>maxLen)
	maxLen = i-start;
	while(s.charAt(start)!=s.charAt(i)){
	//clear the indicator in letterExist from start to the first-time appearance of the found repeated character
	letterExist[s.charAt(start)] = false;
	start++;
	}
	start++;//from next one
	}
	else{
	letterExist[s.charAt(i)] = true;
	}
	}
	if(i==s.length() && i-start>maxLen)
	maxLen = i-start;
	return maxLen;
	}

view raw gistfile1.java hosted with ❤ by GitHub

第一百个题目完成！ 继续加油