Very straightForward Python Solution O(n^2)


  • 0
    F
    class Solution(object):
        def lengthOfLongestSubstringKDistinct(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            if k <= 0 or not s: return 0
            n = len(s)
            if k >= n: return n
            dict = {}
            start = 0
            longest = 0
            for i in xrange(n):
                if s[i] in dict:
                    dict[s[i]] += 1
                else:
                    if len(dict) == k:
                        longest = max(longest, i - start)
                        for j in xrange(start, i):
                            dict[s[j]] -= 1
                            if dict[s[j]] == 0:
                                del dict[s[j]]
                                start = j + 1 #start from j + 1 for the next round 
                                break
                    dict[s[i]] = 1
            return max(longest, n - start)
    

Log in to reply
 

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