3. Longest Substring Without Repeating Characters

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

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

Solution

1. 通过Set来存储已经出现的字符。
2. O(n^2)时间复杂度

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        char[] arr = s.toCharArray();
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < arr.length; i++){
            Set<Character> set = new HashSet<>();
            for(int j = i; j < arr.length; j++){
                if(!set.contains(arr[j]))
                    set.add(arr[j]);
                else{
                    max = Math.max(max, set.size());
                    break;
                }
            }
            max = Math.max(set.size(), max);
        }
        return max;
    }
}

二刷

1. 通过Set来保证没有重复的元素。
2. 使用快慢双指针。
   • 如果集合内没有出现重复元素，则将快指针的值加入集合。
   • 如果集合内出现了重复元素，则将慢指针的值加入集合。
   • 每次指针变化的时候判断当前集合内的值的个数。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        int slow = 0, fast = 0;
        char[] arr = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int max = 0;
        while(fast < arr.length && slow < arr.length){
            if(!set.contains(arr[fast]))
                set.add(arr[fast++]);
            else
                set.remove(arr[slow++]);
            max = Math.max(max, set.size());
        }
        return max;
    }
}

Amazon session

• Method 1: Sliding window=> two pointer

  class Solution {
    public int lengthOfLongestSubstring(String s) {
        int slow = 0, fast = 0;
        char[] arr = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int res = 0;
        while(fast < arr.length){
            char c = arr[fast];
            if(!set.contains(c)){
                set.add(c);
                res = Math.max(res, fast - slow + 1);
            }else{  // currently c is duplicate, we need to move slow.
                set.add(c);
                while(slow < fast && arr[slow] != c){
                    set.remove(arr[slow]);
                    slow++;
                }
                slow++;
            }
            fast++;
        }
        return res;
    }
  }