Leetcode 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

The straight forward method is to count the length of longest substring starts with every element, which has O(n^2) time complexity and hence is not acceptable.

The first solution is to use a dictionary to store the index of repeat characters, so when the character appears again, the length can be get directly. Note the stored indexes need to be updated. This method has time complexity of O(n) and space complexity O(n).

A slightly improved method is to use a list to map all possible characters, which improves the space complexity to O(1). [Reference: kamyu104's GitHub]

Solution 1:

# T:O(n) S:O(n)
class Solution:
    # @param {string} s
    # @return {integer}
    def lengthOfLongestSubstring(self, s):
        if not s:
            return 0
        result, left, d = 0, 0, {}
        for i, ch in enumerate(s):
            if ch in d and d[ch] >= left:
                left = d[ch] + 1
            d[ch] = i
            result = max(result, i - left +1)
        return result 

Run Time: 120 ms

Solution 2:

# T:O(n) S:O(1)
class Solution:
    # @param {string}
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        longest, start, visited = 0, 0, [False for _ in xrange(256)]
        for i, char in enumerate(s):
            if visited[ord(char)]:
                while char != s[start]:
                    visited[ord(s[start])] = False
                    start += 1
                start += 1
            else:
                visited[ord(char)] = True
            longest = max(longest, i - start + 1)
        return longest 

Run Time: 144 ms