Post

Leetcode 3. Longest Substring Without Repeating Characters

Explanation for Leetcode 3 - Longest Substring Without Repeating Characters, and its solution in Python.

Posted
By Hyeonu(Eric) Kim
2 min read

Problem

Leetcode 3 - Longest Substring Without Repeating Characters

Example:

1
2
3
4
5
6
7
8
9
10
11
12

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

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

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Approach

We can approach this problem by using two pointer and set to keep track of unique characters.

We leave the left pointer on the first element of the string and we can iterate through the character in string (as right pointer).

We can add the s[right] into set

  • while s[right] is in set, we can remove s[left] in set then increment left
  • otherwise, we can add s[right] in set then update the maxLength

Visualization of the Approach:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

s = 'abcabcbb'
     l
     r
s_set = (a)
res = 1

s = 'abcabcbb'
     lr
s_set = (a,b)
res = 2

s = 'abcabcbb'
     l r
s_set = (a,b,c)
res = 3

s = 'abcabcbb'
     l  r
Since s[r] is already in set, we increment l and remove s[l]

s = 'abcabcbb'
      l r
s_set = (b,c,a)
res = 3

s = 'abcabcbb'
      l  r
Since s[r] is already in set, we increment l and remove s[l]

s = 'abcabcbb'
       l r
s_set = (c,a,b)
res = 3

s = 'abcabcbb'
       l  r
Since s[r] is already in set, we increment l and remove s[l]

s = 'abcabcbb'
        l r
s_set = (a,b,c)
res = 3

s = 'abcabcbb'
        l  r
Since s[r] is already in set, we increment l and remove s[l]

s = 'abcabcbb'
          lr
s_set = (c,b)
res = 3

s = 'abcabcbb'
          l r
Since s[r] is already in set, we increment l and remove s[l]

s = 'abcabcbb'
            l
            r
s_set = (b)
res = 3

return 3

Here is the Python code for the solution:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        s_set = set()
        res = 0

        for r in range(len(s)):
            while s[r] in s_set:
                s_set.remove(s[r])
                left += 1
            s_set.add(s[r])
            res = max(res, r-left+1)
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$ where $n$ represents the number of characters in string

Space Complexity: $O(m)$ where $m$ represents the number of unique characters in string

Leetcode, Sliding Window, Medium
Leetcode Python Study Sliding Window Medium
This post is licensed under CC BY 4.0 by the author.