Leetcode: Longest Substring without repearting characters

Longest Substring Without Repeating Characters | LeetCode OJ

We only need to keep track of substring that do not have repeated characters

1. Scan the string from left
2. Store index of each character encountered in a dictionary
3. Every time we see a character already present in the dictionary we update the index of the last unique character
4. For each character we find how far it is from the last unique character

Remarks:

1. O(n) time complexity for iterating the string
2. O(n) space complexity for storing the indices of characters

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        res, d, prev = 0, {}, 0
        for i, c in enumerate(s):
            prev = max(prev, d[c] + 1) if c in d else prev
            d[c] = i
            res = max(i + 1 - prev, res)
        return res

A faster solution

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    res, d, prev = 0, {}, 0
    for i, c in enumerate(s):
        if c in d and d[c]>=prev:
            prev = d[c]+1
        d[c] = i
        res = max(i + 1 - prev, res)
    return res