Simple Python two-pointer & dictionary O(n) solution


  • 0
    W

    Two pointers i and j starts from the beginning of s. A dict, "asset", is used to record the chars between s[i] and s[j], inclusive. As j moves, asset increases. Move i if asset is invalid. Now s[i to j] is a valid substring, update the result. Repeat until j hits the end.

    def lengthOfLongestSubstringKDistinct(s, k):
        asset = {}  # {char : count between s[i] and s[j]}
        i = best = 0
        for j in xrange(len(s)):
            asset[s[j]] = asset.get(s[j], 0) + 1
            # move i until asset has at most k distinct chars
            while len(asset) > k:
                asset[s[i]] -= 1
                if asset[s[i]] == 0:
                    del asset[s[i]]
                i += 1
            if len(asset) <= k:
                best = max(best, j - i + 1)
        return best
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.