边工作边刷题：70天一遍leetcode: day 71-1

时间：2022-04-26 12:31:02

Longest Substring with At Most K Distinct Characters

要点：要搞清楚At Most Two Distinct和Longest Substring Without Repeating Characters (No Repeating)的区别：前者的sliding window里只有2个char，但是可以任意重复。而后者可以有任意多个char但是任何char都不能有重复。

  • 所以解法上前者的hashset只有2个元素，而后者需要把所有distinct的元素放到hashset里。而前者因为只有当不在hashset中的元素才可能考虑更新hashset，而后者是有当前元素在hashset里更新。
  • 推广到k，
    • At Most K Distinct要把k个元素中最后一次出现（最右）最靠左的那个去掉，所以要不断更新最右边界，At Most K Repeating因为新元素在hashset中，所以去掉的只能是该元素，只是k扩展到要记录重复的元素个数是否到k才启动。
    • At Most K Distinct还有用count的方法：把集中检查边界分布到从左向右每个元素减少count，最先count减少到0的就是最左。而At Most K Repeating因为只去掉一个元素，没有这个方法。

要点：

  • 是对longest substring without repeating characters这题另一种思路的扩展。no repeating这题是用map存当前sliding window的字符，下一个char不能出现在map中。而distinct这题是下一个不能是没有在map中的（除非map中只有一个or <k个）。
  • k个中选哪个取代？显然k个字符中最后出现中最靠左的字符是所选。这样能保证当前sliding window中的local maxLen
  • 上面的方法每次新字符都要遍历k个在map中的字符，整体时间是O(n)*O(k)。另一种方法更类似no repeating的方法。直接从sliding window左边开始pop直到某个元素count==0（所以map中记录count）。其实也是找到最后出现的最靠左字符。

错误点：

  • start的更新在清楚左边界的loop内，如果没有进入这个清除环节，不需要更新start
  • start的更新在leftMost的+1位置
  • count version不用检查>0，因为在map中的都是如此
  • count version：注意start是index，umap[s[start]]
  • count version: 初始map中的count value是1而不是0
  • count version: 别忘了新元素进map（主要是光想着del key了）

https://repl.it/CaiH (map loop)
https://repl.it/CaiT/1 (k, count)
https://repl.it/CqmA (Two, use char1, char2 variables)

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        n = len(s)
        maxLen = 0
        umap = {}
        start = 0
        for i in xrange(n):
            if s[i] not in umap and len(umap)>=k:
                leftMost = n
                rmChar = None
                for c in umap:
                    if umap[c]<leftMost:
                        leftMost = umap[c]
                        rmChar = c
                del umap[rmChar]
                start = leftMost+1 # error 1: start should be set inside update condition
                                   # error 2: start index: next of leftMost
            umap[s[i]]=i

            if i-start+1>maxLen:
                maxLen = i-start+1
            #print i,start,maxLen,umap
        return maxLen

sol = Solution()
print sol.lengthOfLongestSubstringKDistinct("aabbcc", 1)
print sol.lengthOfLongestSubstringKDistinct("aabbcc", 2)
print sol.lengthOfLongestSubstringKDistinct("aabbcc", 3)
print sol.lengthOfLongestSubstringKDistinct("eceba", 2)
        
# Given a string, find the length of the longest substring T that contains at most k distinct characters.

# For example, Given s = “eceba” and k = 2,

# T is "ece" which its length is 3.

# Hide Company Tags Google
# Hide Tags Hash Table String
# Hide Similar Problems (H) Longest Substring with At Most Two Distinct Characters

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        umap = {}
        if k==0: return 0
        longest, start = 0,0
        for i in xrange(len(s)):
            # print "it=", i,umap,len(umap)
            if s[i] in umap:
                umap[s[i]]+=1
            elif len(umap)<k:
                umap[s[i]]=1 # error 1: should be 1, not 0
            else:
                umap[s[i]]=1 # error 2: don't forget to put myself into
                while start<i:
                    c = s[start]
                    start+=1
                    umap[c]-=1
                    if not umap[c]:
                        del umap[c]
                        break
            longest = max(longest, i-start+1)
        return longest

sol = Solution()
assert sol.lengthOfLongestSubstringKDistinct("eceba", 2)==3

相关文章