Question Link:

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

Qualified Suffix

Assuming the string is s[0,1, ...n-1], instead of finding the qualified substring, we find the qualified suffix. However, the longest suffix strings for each s[i] will give the correct result to the original problem.

Lets define <a, b> is a duplicate pair where s[a] == s[b], then it is not hard to show that, for the character s[i], the longest suffix strings should be s[j..i] where j is the largest b value for all duplicate pairs before s[i].

Implementation

Then we can have following python code. We use hash table to record the last occurrence of each character to keep track the duplicates. The code is very neat and efficient (first time my code beats more than 90%… :p).

[-] Python code accepted by LeetCode OJ 
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = 0
        last_occurrence = {}
        last_duplicate = -1
        for i in xrange(len(s)):
            j = last_occurrence.get(s[i], -1)
            if last_duplicate < j:
                last_duplicate = j
            if n < i - last_duplicate:
                n = i - last_duplicate
            last_occurrence[s[i]] = i

        return n