Longest Substring Without Repeating Characters 

最近在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.

下面是本人的swift实现方法，思路过于麻烦时间复杂度O(n^3);导致在字符串很长的时候超时，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var resoult = 0 ;
        var string = "";
        for i in 0 ..< s.characters.count{
            for j in i+1 ... s.characters.count {
                let indexI = s.index(s.startIndex, offsetBy: i);
                let indexJ = s.index(s.startIndex, offsetBy: j);
                string = s.substring(with: indexI..<indexJ);
                if self.allUnique(string) {
                    resoult = max(resoult, string.characters.count);
                }
            }
        }
        return resoult;
    }
    
    func allUnique(_ string:String) -> Bool {
        var set:Set<Character> = [];
        for i in 0 ..< string.characters.count {
            
            let index = string.index(string.startIndex,offsetBy:i)
            let c = string[index];
            
            if set.contains(c) {
                return false;
            }
            set.insert(c);
        }
        return true;
    }
}

优化：方法2 Sliding Window

The naive approach is very straightforward. But it is too slow. So how can we optimize it?

In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring sij from index i to j - 1 is already checked to have no duplicate characters. We only need to check if s[j] is already in the substring sijs
​ij.
To check if a character is already in the substring, we can scan the substring, which leads to an O(n^2) algorithm. But we can do better.
By using HashSet as a sliding window, checking if a character in the current can be done in O(1).
A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. [i, j) (left-closed, right-open). A sliding window is a window “slides” its two boundaries to the certain direction. For example, if we slide [i, j)to the right by 11 element, then it becomes [i+1, j+1)(left-closed, right-open).
Back to our problem. We use HashSet to store the characters in current window [i, j)(j = i initially). Then we slide the index jj to the right. If it is not in the HashSet, we slide jj further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index ii. If we do this for all ii, we get our answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

Complexity Analysis

Time complexity : O(2n) = O(n). In the worst case each character will be visited twice by i and j.

Space complexity : O(min(m, n)) Same as the previous approach. We need O(k) space for the sliding window, where k is the size of the Set. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m;