LeetCode #3 Longest Substring Without Repeating Characters

Posted on | Post modified | In , , , , , , , , , ,

Problem

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

Examples

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.
1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
1
2
3
4
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.

Solution1

Method: Two Pointers

Time Complexity: O(n)

Space Complexity: O(n)

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
34
35
36
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) <= 1:
            return len(s)
        
        left = 0
        right = 1
        local_max = 0
        count = 1
        word_set = set(s[0])

        while right < len(s):
            if s[right] in word_set:
                local_max = max(local_max, count)
                while s[left] != s[right]:
                    word_set.remove(s[left])
                    left += 1
                    count -= 1
                left += 1
                right += 1
            else:
                word_set.add(s[right])
                right += 1
                count += 1

        local_max = max(local_max, count)

        return local_max

# print(Solution().lengthOfLongestSubstring("abc"))
# print(Solution().lengthOfLongestSubstring("bbbbb"))
# print(Solution().lengthOfLongestSubstring("pwwkew"))

or

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:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) <= 1:
            return len(s)
        
        left = 0
        right = 1
        local_max = 0
        word_set = set(s[0])

        while right < len(s):
            if s[right] in word_set:
                local_max = max(local_max, len(word_set))
                while s[left] != s[right]:
                    word_set.remove(s[left])
                    left += 1
                left += 1
                right += 1
            else:
                word_set.add(s[right])
                right += 1

        local_max = max(local_max, len(word_set))

        return local_max

# print(Solution().lengthOfLongestSubstring("abc"))
# print(Solution().lengthOfLongestSubstring("bbbbb"))
# print(Solution().lengthOfLongestSubstring("pwwkew"))

or

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
34
35
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) <= 1:
            return len(s)
        
        left = 0
        right = 1
        local_max = 0
        word_set = set(s[0])

        while right < len(s):
            if s[right] in word_set:
                cur_count = len(word_set)

                if cur_count > local_max:
                    local_max = cur_count

                while s[left] != s[right]:
                    word_set.remove(s[left])
                    left += 1
                left += 1
                right += 1
            else:
                word_set.add(s[right])
                right += 1

        return local_max if local_max > len(word_set) else len(word_set)

# print(Solution().lengthOfLongestSubstring("abc"))
# print(Solution().lengthOfLongestSubstring("bbbbb"))
# print(Solution().lengthOfLongestSubstring("pwwkew"))

Solution2

Method:

Data Structures: Dictionary

Time Complexity:

Space Complexity:

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:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        global_count = 0
        local_count = 0
        dictionary = {}

        for idx in range(len(s)):
            if s[idx] not in dictionary:
                dictionary[s[idx]] = idx
                local_count += 1
            else:
                if global_count < local_count:
                    global_count = local_count
                
                pre_idx = dictionary[s[idx]]
                dictionary = {}
                local_count = idx - pre_idx
                dictionary[s[idx]] = idx

                for i in range(pre_idx + 1, idx):
                    dictionary[s[i]] = i

        return max(global_count, local_count)

# print(Solution().lengthOfLongestSubstring("bbbbb") == 1)
# print(Solution().lengthOfLongestSubstring("abcabcbb") == 3)
# print(Solution().lengthOfLongestSubstring("pwwkew") == 3)
# print(Solution().lengthOfLongestSubstring("abba") == 2)
# print(Solution().lengthOfLongestSubstring("aab") == 2)

Solution3

Method: Dynamic Programming

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        dic = {}
        res = 0
        pre = 0
        for i, var in enumerate(s):
            if var in dic.keys():
                end = dic[var] + 1
                res = max(i - pre, res)
                while pre < end:
                    del dic[s[pre]]
                    pre += 1
            dic[var] = i

        return max(len(s) - pre, res)