3. Longest Substring Without Repeating Characters.md

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;
    }
}

Third Time

• Method 1: Two pointers + Set

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