Python solution with detailed explanation


  • 0
    G

    Solution

    Longest Substring with At Most K Distinct Characters
    https://leetcode.com/problems/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)):
                freq[s[end]].add(end)
                if len(freq) <= k:
                    max_w = max(max_w, end-start+1)
                else:
                    while start < end and len(freq) > k:
                        freq[s[start]].remove(start)
                        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.