Problem

Given a string, find the length of thelongest substringwithout 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 asubstring,"pwke"is asubsequenceand not a substring.

思路

1. 暴力
   1. 时间复杂度O(n ^ 2)
   2. for the ith element, go back to make a substring and update the length
2. 优化思路(HashSet)
   1. cannot sort, we want a substring not a subsequence
   2. time complexity might be O(n)
   3. for the ith element, we got the end of the substring, so the start of the string is last we need to know
   4. maintain start pointer and end pointer

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Set<Character> hash = new HashSet<>();
        int res = 0;
        int start = 0;
        int end = 0;

        while (end < s.length()) {
            char endCh = s.charAt(end);
            while (hash.contains(endCh)) {
                char startCh = s.charAt(start);
                hash.remove(startCh);
                start++;
            }
            hash.add(endCh);
            end++;
            res = Math.max(res, end - start);
        }
        return res;
    }

HashMap version (follow the template)

• the key is to define the condition
• here the condition is a counter which represent how many extra repeated number
• for example,
  • "abc", counter == 0
  • "abca", counter == 1

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;

        Map<Character, Integer> map = new HashMap<>();

        // count how many extra repeated number
        int count = 0;
        int result = 0;
        int start = 0; 
        int end = 0;

        while (end < s.length()) {
            char ec = s.charAt(end);
            map.put(ec, map.getOrDefault(ec, 0) + 1);
            if (map.get(ec) > 1) count++;
            end++;

            while (count > 0) {
                char sc = s.charAt(start);
                if (map.get(sc) > 1) count--;
                map.put(sc, map.get(sc) - 1);
                start++;
            }
            result = Math.max(result, end - start);
        }
        return result;
    }