LeetCode-Python-159. 最大2つの異なる文字を含む長男列

2059 ワード

1つの文字列sが与えられ、2つの異なる文字を含む最大の長男列tが見出される.
例1:
  : "eceba"
  : 3
  : t   "ece",   3。

例2:
  : "ccaabbb"
  : 5
  : t   "aabbb",   5。

考え方:
観察してみるとsliding windowで解くことができますが、
Windowsの左境界と右境界をleftとrightで表し、
現在windowにある文字をqueueで記録し、
last_でposは現在windowにある文字の最後に現れた下付き文字を記録します.
rightを1つずつ右にスキャンし、新しい要素char=s[right]に遭遇するたびに、
1.charがqueueに既に存在する場合、追加処理が必要でないことを説明し、last_を更新するだけです.pos,last_pos[char] = right
2.charがqueueにいなければ
a.queueのsize<2の場合、空席があることを説明して直接入れてlast_posにlast_を記録するpos[char] = right
b.queueのsize>=2であれば、人を蹴ることを意味し、queueの2つの要素には転がり卵が1つ必要です.
どちらを蹴るかどうやって決めますか?
考え方はLRUに似ています.1つの要素が最後に表示された場合は下付きで3、もう1つの前に表示された場合は下付きで4、現在は下付きで5となります.
3と表示されているものを蹴るべきで、新しい子串がもっと長いことを保証するためです.
class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        left, right = 0, 0
        queue = []
        last_pos = {}
        res = 0
        for right in range(len(s)):
            if s[right] in queue:
                last_pos[s[right]] = right
            elif s[right] not in queue:
                if len(queue) >= 2:

                    if last_pos[queue[0]] < last_pos[queue[1]]: # 0     
                        left = last_pos[queue[0]] + 1
                        last_pos.pop(queue[0])
                        queue.pop(0)
                    else:
                        left = last_pos[queue[1]] + 1
                        last_pos.pop(queue[1])
                        queue.pop(1)
                        
                queue.append(s[right])
                last_pos[s[right]] = right
            # print s[left:right + 1]
            res = max(res, right - left + 1)
        return res
                        
        return res