Python solution with detailed explanation

  • 0


    Longest Substring with At Most K Distinct Characters

    Two Pointer Pattern

    • Use two pointers start and end. Move end to right till you get a valid solution. Then move start to right till you invalidate the solution. Do the necessary book-keeping.
    from collections import defaultdict        
    class Solution(object):
        def lengthOfLongestSubstringKDistinct(self, s, k):
            :type s: str
            :type k: int
            :rtype: int
            if k == 0:
                return 0
            start, end, max_w, freq = 0, 0, 0, defaultdict(set)
            for end in range(len(s)):
                if len(freq) <= k:
                    max_w = max(max_w, end-start+1)
                    while start < end and len(freq) > k:
                        if len(freq[s[start]]) == 0:
                            del freq[s[start]]
                        start += 1
            return max_w  

Log in to reply

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