3. Longest Substring Without Repeating Characters（动态规划，五星），longestrepeating

3. Longest Substring Without Repeating Characters（动态规划，五星），longestrepeating

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.

翻译：给定一个字符串，找出其中没有重复字符的最长子字符串

cbmbbz的做法(复杂度O(n))

public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);//假设如果直接j=map.get(s.charAt(i))+1，也就是直接将j对准该字符串上次出现位置的下一个，然后从j位置开始计算长度。//对于重复字符串中包含另一对重复字符串的情况会出错。如“abba”，当i为3时，j会变为0，得到的长度为4，忽略了中间的bb，//所以j = Math.max(j,map.get(s.charAt(i))+1)，j选择最大值，相当于j选择最靠后的重复位置，免得忽略掉中间的重复字符。
            }
            map.put(s.charAt(i),i);//存储字符及对应位置，若之前存储过该字符，则用新位置替换旧位置
            max = Math.max(max,i-j+1);//当最大长度发生变化时，及时更新
        }
        return max;
    }

我自己的做法，复杂度O(n*n)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set=new HashSet<Character>();
int count=0;
int max=0;
for(int i=0;i<s.length();i++){
count=0;
for(int j=i;j<s.length();j++){
if(!set.add(s.charAt(j)))
break;
count++;
}
max=Math.max(max, count);
set.clear();
}
return max;
    }
}