[leetcode]Longest Substring Without Repeating Characters

新博文地址： [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.

 求最长不重复子串，很经典的DP问题（DP好渣。。。。）

第一反应时用递归：但是时间复杂度还是达到了O(n^2)，leetcode的数据总是强到本地无法测试。。。。，以下是递归实现的代码：

public int lengthOfLongestSubstring(String s) {
        if(s == null || s.isEmpty()){
        	return 0;
        }
        int maxLength = 0;
        int tem = 0;
        int from = 0;
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i = 0 ; i < s.length(); i++){
        	if(!map.containsKey(s.charAt(i))){
        		map.put(s.charAt(i),i);
        		maxLength++;
        	}else{
        		from = map.get(s.charAt(i)); //重复字母上次出现的位置
        		tem = lengthOfLongestSubstring(s.substring(from + 1));
        		break;
        	}
        }
	return maxLength > tem ? maxLength : tem ;
	}

  超时。。。。

下面来看DP实现，由于懒得再写Hash，偷懒用了hashMap，道理是一样的。

public int lengthOfLongestSubstring(String s) {
		int length = s.length();
		Map<Character,Integer> hash = new HashMap<Character,Integer>();
		int currentLength  = 0;
		int maxLength = 0;
		int from = 0;
		for(int i = 0; i < length; i++){
			if(!hash.containsKey(s.charAt(i))){
				currentLength++;
				hash.put(s.charAt(i), i);
			}else{
				if(from <= hash.get(s.charAt(i))){
					from = hash.get(s.charAt(i)) + 1;
					currentLength = i - hash.get(s.charAt(i));
					hash.put(s.charAt(i), i);
				}else{
					currentLength++;
					hash.put(s.charAt(i), i);
				}
			}
			if(currentLength > maxLength){
				maxLength = currentLength;
			}
		}
		return maxLength;
	}