3. Longest Substring Without Repeating Characters

Problem

  • 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.

Thought Process

  • Brute force, nested loop to loop thru all the sub-strings
  • use a list to store sub-string; and a dict whose key is the len of substring, and value is the substring
  • return max len substring

White Board

Below is the white board:

Code

The brute force solution has some issues. But I thought about using shifting window to solve it

class Solution:
    def lswp(self, my_str):
        res = {}
        for i in range(len(my_str)):
            temp = []
            temp.append(my_str[i])
            for j in range(len(my_str)):
                if my_str[j] not in temp:
                    temp.append(my_str[j])
                else:
                    break
            res[len(temp)] = "".join(temp)

        return(max(res))

def test_lswp():
    lswp = Solution().lswp("abcabcbb")
    print(lswp)

test_lswp()    

3

I think this brute force solution is not correct

Complexity

  • Time complexity is O(n**2), two nested loops
  • Space complexity is O(n), as I did create additional dictionary and list to store the results

Optimization

Use shifting-windows, and an ascii array to check if a char exists in the current sub-string

class Solution2:
    def lswp2(self, s):
        freq = [0] * 128
        # use freq to store the freq of all the chars
        l, r = 0, -1
        # shifting window is s[l,r], with invalid init state
        res = 0
        # initially res is 0

        while l < len(s):

            # as long as l can still move to the right

            if((r + 1 < len(s)) and (freq[ord(s[r+1])] == 0)):
                # r can still move to the end
                r += 1
                freq[ord(s[r])] += 1

            else:
                # if s[r+1] already exists, a.k.k freq[ord(s[r+1])] = 1
                # move l until s[r+1] doesn't exist in s[l, r]
                # every l += 1, need to exclude s[l] first, so s[l] is not in s[l,r] no more
                freq[ord(s[l])] -= 1
                l += 1
            res = max(res, r - l + 1)

        if res == 0:
            return 0

        return res

def test_lswp2():
    lswp2 = Solution2().lswp2("xxzqi")
    print(lswp2)

test_lswp2()            

4

Now the time complexity is O(n), space complexity is O(128) => O(1) since I use a space of 128 to store all ascii value