Longest Substring Without Repeating Characters (Medium)

update Feb 17, 2018 15:03

LeetCode

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

Basic Idea:

使用 sliding window 的思路，维持在 left 和 right 之间部分没有重复字符。具体地，用一个 boolean dup 来标记是否有重复，如果有，则不停右移 left 直到去掉重复。右移 right 来扩展window，每次检查是否产生了重复，如果是，则设 dup 为 true。具体地，检查是否有重复的方法是 keep 一个 map 来统计当前window中各个字符的个数。

时间复杂度为 O(n) ，因为每次left和right一定会移动，而且不会向后移。空间复杂度为 O(n)。

在写代码的过程中，要从程序运行的过程中间开始考虑，而不可以从起始时开始考虑，这样整体思路才会更自然。

• Java Code:

    class Solution {
        public int lengthOfLongestSubstring(String s) {
            if (s == null) return 0;
            else if (s.length() < 2) return s.length();
            int[] count = new int[256];
            int left = 0, right = -1, ret = 0;
            boolean dup = false;
  
            while (right < s.length()) {
                while (dup) {
                    if (--count[s.charAt(left)] == 1) {
                        // means before this step, it is 2, which means has duplicate
                        dup = false;
                    }
                    left++;
                }
                // must have no duplicate now
                ret = Math.max(ret, right - left + 1);
                // right shift right pointer
                right++;
                if (right == s.length()) break;
                else if (++count[s.charAt(right)] > 1) {
                    // means has duplicate now
                    dup = true;
                }
            }
            return ret;
        }
    }

_10/15/2024_

注意sliding window的写法

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] arr = s.toCharArray();
        int maxLength = 0;
        int left = 0, right = 0;
        while (right < arr.length) {
          map.put(arr[right], map.getOrDefault(arr[right], 0) + 1);
          right++;
          while (right - left > map.size()) {
            int leftCount = map.get(arr[left]);
            if (leftCount - 1 == 0) map.remove(arr[left]);
            else map.put(arr[left], leftCount - 1);
            left++;
          }
          maxLength = Math.max(maxLength, right - left);
        }
        return maxLength;
    }
}