Leetcode3——Longest Substring Without Repeating Characters

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 subsequence and not a substring.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int count = 0;
        int index = 0;
        //[index,i-1]中是否有与s[i]重复的字符
        boolean flag = false;
        for(int i = 0; i < s.length(); i++) {
            flag = false;
            char ch = s.charAt(i);
            //如果s[j]与s[i]重复，index直接变为j + 1，重新计算不重复字符数
            for(int j = index; j < i; j++) {
                if(s.charAt(j) == s.charAt(i)) {
                    flag = true;
                    index = j + 1;
                    count = i - j;
                    break;
                }
            }
            if(!flag) {
                count++;
                if(count > max) {
                    max = count;
                }
            }
        }
        return max;
    }
}

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Character> map = new HashMap<Character, Character>();
        int max = 0;
        int count = 0;
        int j = 0;
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //如果有重复字符，逐个移除字符，直到移除了与第i个字符重复的字符
            if(map.containsKey(ch)) {
                while(map.containsKey(ch)) {
                    map.remove(s.charAt(j));
                    j++;
                    count--;
                }
                count++;
                map.put(ch, ch);
            }else {
                map.put(ch, ch);
                count++;
                if(count > max) {
                    max = count;
                }
            }
        }
        return max;
    }
}