LC 3 | JZ 48

Solution to LeetCode 3 Longest Substring Without Repeating Characters.

LeetCode 3 | JZ 48

Longest Substring Without Repeating Characters (Medium). [LeetCode link]

The DP function for the max length of unique characters is:

# Pseudocode
if dp[j-1] < j - i: # no duplicate
      dp[j] = dp[j-1] + 1
elif dp[j-1] >= j - i: # duplicate
      dp[j] = j - i

1. DP with HashTable. Use HashTable to update the index of each character. Time complexity O(N), space complexity O(1).

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        Hash = {}
        res = tmp = 0
        for j in range(len(s)):
            i = Hash.get(s[j], -1) # get the index 
            Hash[s[j]] = j # update the index
            if tmp < j - i:
                tmp += 1
            elif tmp >= j - i:
                tmp = j - i
            res = max(res, tmp) # max(dp[j - 1], dp[j])
        return res

2. DP with Double Pointers. Time complexity O(N), space complexity O(1).

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        Hash = {}
        res = 0
        i = -1
        for j in range(len(s)):
            if s[j] in Hash:
                i = max(Hash[s[j]], i) # update left pointer
            Hash[s[j]] = j # update index
            res = max(res, j-i)
        return res